郑州网站建设优化企业,国产做爰全免费的视频网站,深圳网站建设的服务怎么样,浙江宝业建设集团网站有 n 个气球#xff0c;编号为0 到 n-1#xff0c;每个气球上都标有一个数字#xff0c;这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i #xff0c;就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻…有 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 315 358 138 181 167
解题思路
数组含义dp[i][j]在【ij】区间内获得硬币的最大值 状态转移 dp[i][j] Math.max(dp[i][j],dp[i][k-1]dp[k1][j]helper[k]helper[i-1]helper[j1]); 在【ij】区间内选择不同的位置k作为最后一个戳破的气球那么k两边的气球区间都要被全部戳破 选择最优的位置k取得当前区间的最优解。 初始化考虑到边界问题将nums首尾多加两个的1*
代码
class Solution {public int maxCoins(int[] nums) {int nnums.length;if(n0) return 0;int[][] dpnew int[n2][n2];int[] helpernew int[n2];helper[0]helper[n1]1;for(int i0,j1;jn;i,j)helper[j]nums[i];for(int len1;lenn;len)for(int i1;ilen-1n;i){int jilen-1;for(int ki;kj;k)dp[i][j] Math.max(dp[i][j],dp[i][k-1]dp[k1][j]helper[k]*helper[i-1]*helper[j1]);}return dp[1][n];}
}
