前言

想要精通算法和SQL的成长之路 - 系列导航

一. 戳气球

原题链接

首先我们看一下题干：对于超出了数组边界的，就当做它是一个数字为1的气球。遇到这种的，我们可以考虑给数组边界添加哨兵。其值为1。

// 左右各加一个哨兵节点
public int maxCoins(int[] nums) {// 1.先处理特殊情况if (nums.length == 1) {return nums[0];}int len = nums.length;// 左右各加一个哨兵节点int[] arr = new int[len + 2];arr[0] = 1;arr[len + 1] = 1;for (int i = 1; i < len + 1; i++) {arr[i] = nums[i - 1];}return ???
}

其次，我们假设有这么一个函数dfs，代表在(left,right)开区间内，可以获得的最大硬币数量。为啥是开区间？因为我们为数组添加了两个哨兵，这俩哨兵不应该在处理范围内。同时，设置俩哨兵的意义也就是：我们认定，每次戳气球的时候，必定存在至少3个气球（有两个可能是哨兵气球）

// nums 在(left,right)开区间内戳气球
public int dfs(int[] nums, int left, int right) {
}

那么，dfs递归，我们首先要写的就是他的递归终止条件：

// 气球数量不足3个
if (right - left < 2) {return 0;
}
// 气球数量正好3个
if (right - left == 2) {// 我们只能戳破中间的气球（左右两侧是哨兵），获得对应硬币数量return nums[left] * nums[left + 1] * nums[right];
}

其次，dfs递归，我们做啥事情？根据前面的递归终止条件可以判断出，此时气球的数量必定 > 3个。我们假设戳气球的步骤：

1. 先把第k个气球的左侧给戳破完，那么左侧区域能获得的最大硬币数量为：dfs(nums, left,k)。
2. 再把第k个气球的右侧给戳破完，那么右侧区域能获得的最大硬币数量为：dfs(nums, k,right)。
3. 最后戳破第k个气球，那么戳破当前气球获得的硬币数量为：nums[k] * nums[left] * nums[right]。

那么写成代码就是：

// nums 在(left,right)开区间内戳气球
public int dfs(int[] nums, int left, int right) {int res = 0;// 气球数量不足3个if (right - left < 2) {return 0;}// 气球数量正好3个if (right - left == 2) {return nums[left] * nums[left + 1] * nums[right];}// 在[left+1,right-1]闭区间内遍历，选取每次遍历的当前节点作为 最后戳破 的气球（最后戳破。最后戳破。最后戳破）for (int k = left + 1; k < right; k++) {// 戳破第k个气球，该气球左侧的最大硬币数int leftCount = dfs(nums, left, k);int rightCount = dfs(nums, k, right);int currentFinalCount = nums[k] * nums[left] * nums[right];res = Math.max(res, leftCount + rightCount + currentFinalCount);}return res;
}

最终的完整代码：

public int maxCoins(int[] nums) {// 1.先处理特殊情况if (nums.length == 1) {return nums[0];}int len = nums.length;// 左右各加一个哨兵节点int[] arr = new int[len + 2];arr[0] = 1;arr[len + 1] = 1;for (int i = 1; i < len + 1; i++) {arr[i] = nums[i - 1];}return dfs(arr, 0, len + 1);
}// nums 在(left,right)开区间内戳气球
public int dfs(int[] nums, int left, int right) {int res = 0;// 气球数量不足3个if (right - left < 2) {return 0;}// 气球数量正好3个if (right - left == 2) {return nums[left] * nums[left + 1] * nums[right];}// 在[left+1,right-1]闭区间内遍历，选取每次遍历的当前节点作为 最后戳破 的气球（最后戳破。最后戳破。最后戳破）for (int k = left + 1; k < right; k++) {// 戳破第k个气球，该气球左侧的最大硬币数int leftCount = dfs(nums, left, k);int rightCount = dfs(nums, k, right);int currentFinalCount = nums[k] * nums[left] * nums[right];res = Math.max(res, leftCount + rightCount + currentFinalCount);}return res;
}

1.1 记忆化搜索

和 填充书架 一样，我们在dfs递归的时候，有大量的重复计算，我们用一个全局的dfsCache做一下缓存即可。

dfsCache的初始化：

dfsCache = new int[len + 2][len + 2];
for (int i = 0; i < len + 2; i++) {Arrays.fill(dfsCache[i], -1);
}

dfsCache的作用体现：如果发现计算过这个值，直接返回，后续的递归直接不用做了。

if (dfsCache[left][right] != -1) {return dfsCache[left][right];
}

完整代码：

public class Test312 {int[][] dfsCache;public int maxCoins(int[] nums) {// 1.先处理特殊情况if (nums.length == 1) {return nums[0];}int len = nums.length;// 左右各加一个哨兵节点int[] arr = new int[len + 2];arr[0] = 1;arr[len + 1] = 1;for (int i = 1; i < len + 1; i++) {arr[i] = nums[i - 1];}dfsCache = new int[len + 2][len + 2];for (int i = 0; i < len + 2; i++) {Arrays.fill(dfsCache[i], -1);}return dfs(arr, 0, len + 1);}// nums 在(left,right)开区间内戳气球public int dfs(int[] nums, int left, int right) {int res = 0;// 气球数量不足3个if (right - left < 2) {return 0;}// 气球数量正好3个if (right - left == 2) {return nums[left] * nums[left + 1] * nums[right];}if (dfsCache[left][right] != -1) {return dfsCache[left][right];}// 在[left+1,right-1]闭区间内遍历，选取每次遍历的当前节点作为 最后戳破 的气球（最后戳破。最后戳破。最后戳破）for (int k = left + 1; k < right; k++) {// 戳破第k个气球，该气球左侧的最大硬币数int leftCount = dfs(nums, left, k);int rightCount = dfs(nums, k, right);int currentFinalCount = nums[k] * nums[left] * nums[right];res = Math.max(res, leftCount + rightCount + currentFinalCount);}return dfsCache[left][right] = res;}