Java DP With Complete Thought Process
Idea\nFirst thought - greedy doesn\'t work - try bursting larger one first in [3,5], but bursting smaller on also doesn\'t work [3,5,8].\n\nSo that tells we nee
**Idea**\nFirst thought - greedy doesn\'t work - try bursting larger one first in [3,5], but bursting smaller on also doesn\'t work [3,5,8].\n\nSo that tells we need to try all possibilities. That is, `[0,...,n-1]`, we check coins in bursting 0th first or bursting 1st balloon first etc..\nSo let us try to define a recurse relation `For k in [0..n-1], maxCoins(k) = ..` but wait how do we know the neighbors for `k` in the optimal path...we need that to calculate the coins given by bursting `k`.\n\nMay be, we can reformulate our strategy which can gurantee our neighbors at `i`. If we define `maxCoins at k` as the case with last guy standing at `k`? We try to place everyone from `[0..n-1]` as last guys, so we know we are tring all possibilities. But this also gurantees, we bursted all the balloons in left part and also in the right part and lastly come to `k`.\n\nSo if we define `maxCoins(i,j) as bursting all balloons in [i..k-1] and in [k+1..j] and then bursting k for all k in [i..j]`, we can define recurrence relation as `maxCoins(i,k-1)+maxCoins(k+1,j)+nums[i-1]*nums[k]*nums[j+1]`.\n\nWhy would `nums[i-1]` and `nums[j+1]` be our neighbors and not burst before `k`? That again stems from the recurrence relation bursting `k` as the last balloon, so the subproblem `maxCoins(i,k-1)` can safely assume `k` (sub-problem neighbour) will be there for product calculation part.\n\n---\n\n\n```\nclass Solution {\n    Integer[][] dp = null;\n\tpublic int maxCoins(int[] nums) {\n\t\tint n = nums.length;\n\t\tdp = new Integer[n][n];\n\t\treturn maxCoins(nums, 0, n - 1);\n\t}\n\tprivate int maxCoins(int[] n, int i, int j) {\n\t\tif (i > j)\n\t\t\treturn 0;\n\t\tif (dp[i][j] != null)\n\t\t\treturn dp[i][j];\n\t\tdp[i][j] = 0;\n\t\tfor (int k = i; k <= j; k++) {\n\t\t\tint prod = n[k];\n\t\t\tif (i - 1 >= 0)\n\t\t\t\tprod *= n[i - 1];\n\t\t\tif (j + 1 < n.length)\n\t\t\t\tprod *= n[j + 1];\n\t\t\tdp[i][j] = Math.max(dp[i][j], maxCoins(n, i, k - 1) + prod + maxCoins(n, k + 1, j));\n\t\t}\n\t\treturn dp[i][j];\n\t}\n}\n```
[]