本文共 1621 字,大约阅读时间需要 5 分钟。
在某射击场有N个靶,每个靶上都有一个分数,存在score数组中,击中第i个靶的得分为core[left]*score[i]*score[right],同时原left和right两个靶变为相邻的靶,其中得分为0的靶是不能射击的,当left不存在或者不能射击时,得分为score[i]*score[right],同理,right也遵循此规则,当left和right都不存在或者都不能射击时,得分为score[i],请计算出击中所有能射击的靶,最多得多少分?
分析:
因为得分0的靶是不能射击的,就好比用“0”隔开,然后一个数组变成多个数组。把每一个段的相加就是最后的结果了,就好比例子[2,3,0,3],把划分开的数组{2,3} {3} 送入leetcode的Burst Balloons题目里面。然后在求和。区间动态规划。
给定n个气球,下标为0到n-1。每个气球上都标有一个数字,用数组nums表示。你被要求扎破所有气球。扎破第i个气球可以获得nums[left] * nums[i] * nums[right]枚硬币。这里left和right是与i相邻的下标。扎破气球以后,left和right就变成相邻的了。
寻找最优策略下可以获得的硬币数。
注意:
(1) 你可以假设nums[-1] = nums[n] = 1. 它们并非真实的因此不能扎破。
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
动态规划(Dynamic Programming)
时间复杂度O(n ^ 3)
以最后被爆破的气球m为界限,把数组分为左右两个子区域
状态转移方程:
dp[l][r]表示扎破(l, r)范围内所有气球获得的最大硬币数,不含边界;
l与r的跨度k从2开始逐渐增大;
三重循环依次枚举范围跨度k,左边界l,中点m;右边界r = l + k;
public class Solution { public int maxCoins(int[] iNums) { int[] nums = new int[iNums.length + 2]; int n = 1; for (int x : iNums) if (x > 0) nums[n++] = x; nums[0] = nums[n++] = 1; int[][] dp = new int[n][n]; for (int k = 2; k < n; ++k) for (int left = 0; left < n - k; ++left) { int r = left + k; for (int m = left + 1; m < r; ++m) dp[left][r] = Math.max(dp[left][r], nums[left] * nums[m] * nums[r] + dp[left][m] + dp[m][r]); } return dp[0][n - 1]; }}参考:
http://bookshadow.com/weblog/2015/11/30/leetcode-burst-balloons/
http://www.cnblogs.com/njufl/p/LeetCode.html
http://blog.csdn.net/zly9923218/article/details/51059664