DFS -> DP Progression with Explanation [O(n^3)/O(n^2)]
In this problem, we are tasked with finding the combination of balloon poppings that yield the highest score.  Thus, we can solve this problem by looking throug
In this problem, we are tasked with finding the combination of balloon poppings that yield the highest score.  Thus, we can solve this problem by looking through all combinations of balloons to pop and returning the highest scoring combination.  DFS is a great tool for this as we can imagine an instance of the function as the current state, and each recursive call as a possible action to another state.  To look through all combinations, the branching would look as follows\n![image](https://assets.leetcode.com/users/images/8983a4d2-6bb3-41b2-a234-e807307cbd27_1604976784.859566.png)\nFrom this, we can derive the dfs solutions with some boundary conditions\n```\ndef dfs(nums):\n\tif not nums:\n\t\treturn 0\n\tif len(nums) == 1:\n\t\treturn nums[0]\n\tscore = 0\n\tfor i in range(len(nums)):\n\t\tcurr = nums[i]\n\t\tif i - 1 >= 0:\n\t\t\tcurr *= nums[i - 1]\n\t\tif i + 1 < len(nums):\n\t\t\tcurr *= nums[i + 1]\n\t\tcurr += dfs(nums[:i] + nums[i + 1:])\n\t\tscore = max(score, curr)\n\treturn score\nreturn dfs(nums)\n```\nThis follows the usual DFS pattern, where we traverse from the root -> leaf, and acquire some _cost_ at each node.  In this case, the cost would be the score from bursting a certain balloon.  Therefore this problem is looking the root -> leaf path that has a maximal cost.  However, this DFS implementation is far too slow and times out.  Why is that?  Imagine we had the following paths:\n```\nnums=[a,b,c,d,e]\n[a,b,c,d,e] --- a ---> [b,c,d,e] --- b ---> [c,d,e]\n[a,b,c,d,e] --- b ---> [a,c,d,e] --- a ---> [c,d,e]\n```\nAfter two steps, both of these paths have popped `a` and `b` and have `[c,d,e]` balloons remaining.  Up to this point the two path\'s scores can be different, but from `[c,d,e]` onwards, both paths will return the same answer.  Our implementation of DFS is not aware of this, and will waste time calculating the same answer for subproblem `[c,d,e]`.  Instead, we can save the solution to a subproblem so we can simply reference it later instead of recalculating it.  This is where the DP approach comes in.\n\nUnfortunately, the DP approach for this problem is **hard**, but also quite revealing.  Usually in dynamic programming problems, we can solve a problem `[a,b,c]` by looking at its subproblems `[a,b]` and `[b,c]`.  This is fine as at this point, we know the solution to `[a,b]` and `[b,c]` which can nicely be stored in a 2D array.  The issue we have with our balloon problem is we need to **also** consider `[a,c]` as a viable subproblem.  This is because we have the recusive relation `dfs(nums[:i] + nums[i + 1:]`, rather than something like `dfs(nums[i + 1:]` or `dfs(nums[:i]`.\nThe solution to this problem is similar to a method used in _chain matrix multiplication_, described in pages 174-175 [here](http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf).  In essense, we have some some array `[a,b,c]`, and we want to find the index `k` that leads us to the maximal score path.  We iterate over the array `let k = [0, 1, 2]` and make the calculations based on popping the `kth` balloon.  Well what happens when we pop the `k = 1` `b` balloon?  This would result in `[a,c] + (a * b * c)`.  But wait!  We run into the same subproblem from earlier `[a,c]` which doesn\'t fit into our 2D array.  How can we retain the balloons positions but still recurse down to find the solution?\nInstead of popping the `kth` balloon and looking at the resulting balloons we have left, let\'s instead say we will pop the `kth` balloon _last_, popping every other balloon in the array before the `kth` balloon.  For an array `[a,b,c,d]`, picking `k` at random would look like\n![image](https://assets.leetcode.com/users/images/fca87669-adcc-461a-87d8-27d7dca1f280_1605029091.778375.png)\nNotice that popping the `kth` balloon results in multiplying by `nums[i - 1] * nums[j + 1]` which are the balloons that would be present if you popped the `kth` balloon last.  In code, we would then have\n```\ndef dp(nums):\n\tA = [[0] * len(nums) for _ in range(len(nums))]\n\tfor i in range(len(nums) - 1, -1, -1):\n\t\tfor j in range(i, len(nums)):\n\t\t\tfor k in range(i, j + 1):\n\t\t\t\tleft = right = 0\n\t\t\t\tif k > i:\n\t\t\t\t\tleft = A[i][k - 1]\n\t\t\t\tif k < j:\n\t\t\t\t\tright = A[k + 1][j]\n\t\t\t\tmid = nums[k]\n\t\t\t\tif i - 1 >= 0:\n\t\t\t\t\tmid *= nums[i - 1]\n\t\t\t\tif j + 1 < len(nums):\n\t\t\t\t\tmid *= nums[j + 1]\n\t\t\t\tA[i][j] = max(A[i][j], left + mid + right)\n\treturn A[0][-1]\nreturn dp(nums)\n```\nThis problem is definitely hard and unusual, but the principles of DP are the same.  We want to find some way to utilize subproblems to solve larger problems, where we can conveniently save the subproblems in an array.  Of course, this problem could also be solved efficiently if we simply introduced memoization with DFS.
['Dynamic Programming', 'Depth-First Search', 'Python']