burst balloon有人做了么？答安都没太看懂 ：（

burst balloon有人做了么？答安都没太看懂 ：（

用DP的方法做，设一个二维数组来保存从第i个气球到第j个气球burst之后的结果。假设是dp[i][j]， 最终的答案就是dp[0][n - 1]（n个气球），然后因为头和尾在burst的时候，旁边相当于是1，所以把input的数组，头尾补上1.
然后求dp[i][j]的过程就是，从i到j扫一遍，k = i to j， 我们把第k位当成是最后burst的点，这时候，k位左边的，和k位右边的都已经消失了，所以num[k] * num[i - 1] * num[j + 1]是最后这次burst的值。之前burst的值你就可以通过dp[i, k - 1] + dp[k + 1, j] 来得到（这就是递推式子）。知道了怎么递推的，后面应该就好写了。

我看的这里：

ans = Math.max(ans, nums[left] * nums[i] * nums[right]
        + burst(memo, nums, left, i) + burst(memo, nums, i, right));

是burst(memo,nums,left,i) 而不是 i-1
burst(memo, nums, i, right));这里也是，是i,不是i＋1
感觉有重复阿？

dimi 发表于 2016-3-28 04:18
我看的这里：

ans = Math.max(ans, nums[left] * nums * nums[right]

额。思路理解了不用太纠结脚标……看你这两行代码是用递归的方法做的，有可能代码前面操作不一样，不好说。

请教这样的题目，面试会出现么