LeetCode 312.戳气球
>
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
>
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
>
求所能获得硬币的最大数量。
> 编者注：请务必理解题意，题目的要求是返回 所有可能 中的 最大值，气球被戳爆后，在下一状态是不存在的，[2 3 1 4] -> [2 3 4]
动态规划 (容易理解)
推荐配合 郭郭老师 的 视频 理解动归的思路
代码语言：javascript复制public int maxCoins(int[] nums) {
int len = nums.length;
int[] arr = new int[len 2];
int[][] dp = new int[len 2][len 2];
System.arraycopy(nums, 0, arr, 1, len);
arr[0] = arr[len 1] = 1;
// 枚举右指针，从下往上填表
for (int left = len - 1; left >= 0; left--) {
for (int right = left 2; right <= len 1; right ) {
// 枚举 (left, right) 间的每个位置，作为最后戳爆的气球
// 1 3 1 5 8 1
// 若 5 为最后一个 则结果为 1*5*1 (1 3 1 5) 和 (5 8 1) 两个情况的结果
// 因此状态转移方程为
// dp[left][right] = dp[left][mid] dp[mid][right] currRs
// 因为 mid ∈ (left, right), 因此每次结果会不同，维护最大值
for (int mid = left 1; mid < right; mid ) {
int sum = arr[left] * arr[mid] * arr[right];
sum = dp[left][mid] dp[mid][right];
dp[left][right] = Math.max(dp[left][right], sum);
}
}
}
return dp[0][len 1];
}记忆化搜索
代码语言：javascript复制public int maxCoins(int[] nums) {
int len = nums.length;
// 设置哨兵
int[] arr = new int[len 2];
System.arraycopy(nums, 0, arr, 1, len);
arr[0] = 1;
arr[len 1] = 1;
int[][] memo = new int[len 2][len 2];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return solve(arr, memo, 0, len 1);
}
private int solve(int[] arr, int[][] memo, int left, int right) {
// 确保至少有三个，即中间至少有一个元素
if (left 1 >= right) {
return 0;
}
// 记忆化搜索
if (memo[left][right] != -1) {
return memo[left][right];
}
for (int i = left 1; i < right; i ) {
int sum = arr[left] * arr[i] * arr[right];
sum = solve(arr, memo, left, i) solve(arr, memo, i, right);
memo[left][right] = Math.max(memo[left][right], sum);
}
return memo[left][right];
}
