admin 管理员组

文章数量: 1087652

LeetCode312：戳气球

要求

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量

思路

只要涉及求最值，没有任何奇技淫巧，一定是穷举所有可能的结果，然后对比得出最值。
穷举主要有两种算法，就是回溯算法和动态规划，前者就是暴力穷举，而后者是根据状态转移方程推导「状态」

方法一：回溯算法
我们其实就是想穷举戳气球的顺序，不同的戳气球顺序可能得到不同的分数，我们需要把所有可能的分数中最高的那个找出来

class Solution {  //O(n!) 超时public int maxCoins(int[] nums) {int[] state = new int[nums.length];for(int i = 0;i<nums.length;i++){state[i] = 0;}tryGetCoins(nums,state,0);return max;}int max = 0;void tryGetCoins(int[] nums, int[] state,int current){int[] tempState = state.clone();int i = 0;if(finished(state)){max = Math.max(max,current);return;}for(i=0;i<nums.length;i++){if(state[i] == 1)continue;tempState[i] = 1;tryGetCoins(nums,tempState,current+getCoinsAt(nums,state,i));copyArray(tempState,state);}}int getCoinsAt(int[] nums,int[] state,int i){int j = 0,result = nums[i];for(j = i-1;j>-1;j--){if(state[j] == 0){result *= nums[j];break;}}for(j = i+1;j<state.length;j++){if(state[j] == 0){result *= nums[j];break;}}return result;}void copyArray(int[] dest,int[] origin){for(int i = 0; i<dest.length;i++){dest[i] = origin[i];}}boolean finished(int[] state){boolean finished = true;for(int i = 0; i < state.length;i++){if(state[i] == 0)finished = false;}return  finished;}
}

当我们回溯完所有的戳法之后，就能找出最大得分。但是该回溯法的时间复杂度显然为O(n!)，而气球个数的取值为[0,500]，必然会有超时的问题。

方法二：动态规划
我们每戳破一个气球 nums[i]，得到的分数和该气球相邻的气球 nums[i-1] 和 nums[i+1] 是有相关性的。但运用动态规划算法的一个重要条件：子问题必须独立。所以必须巧妙地定义 dp 数组的含义，避免子问题产生相关性，才能推出合理的状态转移方程。
数组两端加入新的虚拟气球，形成一个新的数组 points，现在气球的索引变成了从 1 到 n，points[0] 和 points[n+1] 可以认为是两个「虚拟气球」

状态定义：dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（不包括 i 和 j）的所有气球，获得的最高分数为 x。 base case 就是 dp[i][j] = 0，其中 0 <= i <= n+1, j <= i+1，开区间 (i, j) 中间没有气球可以戳。

// base case 已经都被初始化为 0
int[][] dp = new int[n + 2][n + 2];

推导状态转移方程：
假设 k 是气球 i 和气球 j 之间的所有气球最后被戳破的那一个，需要先把开区间 (i, k) 的气球都戳破，再把开区间 (k, j) 的气球都戳破；最后剩下的气球 k，相邻的就是气球 i 和气球 j，这时候戳破 k 的话得到的分数就是 points[i]*points[k]*points[j]。
dp[i][j] 的值应该为：dp[i][k] + dp[k][j] + points[i]*points[k]*points[j]

由于是开区间，dp[i][k] 和 dp[k][j] 不会影响气球 k；而戳破气球 k 时，旁边相邻的就是气球 i 和气球 j 了，最后还会剩下气球 i 和气球 j，这也恰好满足了 dp 数组开区间的定义。
对于一组给定的 i 和 j，我们只要穷举 i < k < j 的所有气球 k，选择得分最高的作为 dp[i][j] 的值即可
dp[i][j] 所依赖的状态是 dp[i][k] 和 dp[k][j]，那么我们必须保证：在计算 dp[i][j] 时，dp[i][k] 和 dp[k][j] 已经被计算出来了（其中 i < k < j）。


选择从下往上遍历

public class LeetCode312 {public int maxCoins(int[] nums) {int n = nums.length;//添加两侧的虚拟气球int[] points = new int[n + 2];points[0] = points[n+1] = 1;//遍历数组赋值for (int i =1; i <= n ; i++) {points[i] = nums[i-1];}//base case初始化为0int[][] dp = new int[n+2][n+2];//i从下往上升for (int i = n; i >= 0; i--) {//j从从左往右for (int j = i + 1; j < n + 2; j++) {//戳破哪个气球for (int k = i + 1; k < j; k++) {//则优做选择dp[i][j] = Math.max(dp[i][j],dp[i][k] + dp[k][j] + points[i]*points[j]*points[k]);}}}return dp[0][n+1];}
}

本文标签： LeetCode312戳气球

版权声明：本文标题：LeetCode312：戳气球 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1687331000a90375.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。