戳气球

描述有 n 个气球编号为0 到 n-1每个气球上都标有一个数字这些数字存在数组 nums 中。现在要求你戳破所有的气球。每当你戳破一个气球 i 时你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后气球 left 和气球 right 就变成了相邻的气球。求所能获得硬币的最大数量。说明:你可以假设 nums[-1] nums[n] 1但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100示例:输入: [3,1,5,8] 输出: 167 解释: nums [3,1,5,8] -- [3,5,8] -- [3,8] -- [8] -- [] coins 3*1*5 3*5*8 1*3*8 1*8*1 167思路分析参考链接https://blog.csdn.net/u014626513/article/details/81146851解法动态规划DP有三重循环。第一重循环是确定每个阶段所截取的每组气球的个数第二重循环是确定分组获得每组气球的起始下标第三重循环是选择刺破的气球下标State: dp[i][j]表示打爆区间[i,j]中的所有气球能得到的最多金币。题目中说明了边界情况当气球周围没有气球的时候旁边的数字按1算这样我们可以在原数组两边各填充一个1这样方便于计算。Function: dp[i][j] max(dp[i][j], nums[i - 1]*nums[k]*nums[j 1] dp[i][k - 1] dp[k 1][j]) ( i ≤ k ≤ j )Return: dp[1][n]中其中n是两端添加1之前数组nums的个数。代码实现publicclassSolution{publicintmaxCoins(int[]iNums){intniNums.length;int[]numsnewint[n2];for(inti0;in;i)nums[i1]iNums[i];nums[0]nums[n1]1;int[][]dpnewint[n2][n2];for(intk1;kn;k){//第一重循环是确定每个阶段所截取的每组气球的个数for(inti1;in-k1;i){//第二重循环是确定分组获得每组气球的起始下标intjik-1;for(intxi;xj;x){//第三重循环是选择刺破的气球下标dp[i][j]Math.max(dp[i][j],dp[i][x-1]nums[i-1]*nums[x]*nums[j1]dp[x1][j]);}}}returndp[1][n];}}