题目一
力扣第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 的气球。
求所能获得硬币的最大数量。
示例1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例2：
输入：nums = [1,5]
输出：10
这个题第一时间可能会想到这样的解： 有一个函数f，参数是L和R，f(L, R)表示从L到R戳爆所有的气球得出的最大分数 然后函数里面可能会枚举每个位置戳爆，然后继续调递归 但是戳爆时的得分是算不准的，因为此时不知道左边最近的一个气球和右边一个最近的气球是哪个（中间可能有已经被戳爆的） 那么可能想到要参数f(L, R，左边没爆的气球，右边没爆的气球) 这样子，参数一下子就变复杂了，因为后面两个参数的变化范围太多了
那么修改一下f函数的含义，f(L, R)表示从L到R戳爆所有的气球得出的最大分数，范式必须保证L-1和R+1位置的气球没爆
而枚举的可能性不是现在要打爆的，而是最后一个要被打爆的气球
比如现在有数组 [2, 3, 5, 2, 1]，现在决定最后打爆3，那么递归调f(0, 0)和f(2, 4)，得到这个尝试的答案 f(0, 0) + 3 + f(2, 4)
为了简便，拷贝原数组，左右两边补一个1，这两个1永远不爆，去枚举中间的位置
/**
* 暴力递归
*/
public static int maxCoins1(int[] arr) {
if (arr == null || arr.length == 0) return 0;
if (arr.length == 1) return arr[0];
/*
copy一个长度加2的数组，左右两边补1，保证左右两边有不被打爆的气球
然后求中间范围的最大值
*/
int[] newArr = new int[arr.length + 2];
newArr[0] = 1;
newArr[newArr.length - 1] = 1;
for (int i = 1; i <= newArr.length-2; i++) {
newArr[i] = arr[i - 1];
}
return process1(arr, 1, newArr.length-2);
}
/**
* 暴力递归
*/
private static int process1(int[] arr, int L, int R) {
// base case L~R范围内只剩一个气球没爆
if (L == R) return arr[L - 1] * arr[L] * arr[R + 1];
// 先单独枚举 最左侧气球最后打爆，最右侧气球最后打爆，求最大得分
int max = Math.max(
arr[L - 1] * arr[L] * arr[R + 1] + process1(arr, L + 1, R),
arr[L - 1] * arr[R] * arr[R + 1] + process1(arr, L, R - 1)
);
/*
枚举中间每一个位置，作为最后被打爆的气球
然后递归
抓出最大值
*/
for (int i = L + 1; i < R; i++) {
max = Math.max(max, arr[L - 1] * arr[i] * arr[R + 1]
+ process1(arr, L, i - 1)
+ process1(arr, i + 1, R));
}
return max;
}
然后就可以改成动态规划版本的解
记忆化搜索版本：
/**
* 改成记忆化搜索的版本
*/
public static int maxCoins2(int[] arr) {
if (arr == null || arr.length == 0) return 0;
if (arr.length == 1) return arr[0];
int[] newArr = new int[arr.length + 2];
newArr[0] = 1;
newArr[newArr.length - 1] = 1;
for (int i = 1; i <= newArr.length-2; i++) {
newArr[i] = arr[i - 1];
}
int[][] dp = new int[newArr.length][newArr.length];
return process2(arr, 1, newArr.length-2, dp);
}
/**
* 改成记忆化搜索的版本
*/
private static int process2(int[] arr, int L, int R, int[][] dp) {
if (dp[L][R] != 0) return dp[L][R];
if (L == R) {
dp[L][R] = arr[L - 1] * arr[L] * arr[R + 1];
return arr[L - 1] * arr[L] * arr[R + 1];
}
int max = Math.max(
arr[L - 1] * arr[L] * arr[R + 1] + process1(arr, L + 1, R),
arr[L - 1] * arr[R] * arr[R + 1] + process1(arr, L, R - 1)
);
for (int i = L + 1; i < R; i++) {
max = Math.max(max,
arr[L - 1] * arr[i] * arr[R + 1]
+ process1(arr, L, i - 1)
+ process1(arr, i + 1, R));
}
dp[L][R] = max;
return max;
}
严格的动态规划：
class Solution {
public int maxCoins(int[] nums) {
int[] temp = new int[nums.length+2];
temp[0] = 1;
temp[temp.length-1] = 1;
for (int i = 0; i < nums.length; i++) {
temp[i+1] = nums[i];
}
int[][] dp = new int[nums.length+2][nums.length+2];
for (int i = 3; i <= nums.length+2; i++) {
for (int j = 0; j <= nums.length+2-i; j++) {
int res = 0;
for (int k = j+1; k < j + i -1; k++) {
int left = dp[j][k];
int right = dp[k][j+i-1];
int value = temp[j] * temp[k] * temp[j + i -1];
int result = left + value + right;
res = Math.max(res, result);
}
dp[j][j+i-1] = res;
}
}
return dp[0][nums.length+1];
}
}
这一题解题关键就是补充了两个前提：
1、 L-1和R+1没爆；
2、 枚举的是最后一个没爆的气球；
题目二
力扣第546题
https://leetcode.cn/problems/remove-boxes/description/
给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。
返回你能获得的最大积分和 。
示例1：
输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)
示例2：
输入：boxes = [1,1,1]
输出：9
示例3：
输入：boxes = [1]
输出：1
这一题，也是依赖到左边信息和右边信息的，如果没有左边信息和右边信息，就没法准确得出最优得分，比如L~R范围上消除，但是L-1及其前面可能有连成一片与L相同的，但是我们不知道，右边也是。
因此需要引入外部信息，但是要让外部信息尽量简单，增加一个K参数，表示前面有K个数，与boxes[L]相同。
class Solution {
public int removeBoxes(int[] boxes) {
int N = boxes.length;
int[][][] dp = new int[N][N][N];
return process(boxes, 0, N - 1, 0, dp);
}
/**
* 前面跟着K个boxes[L]，消掉L~R的最高得分
* @param boxes 盒子数组
* @param L 左边界
* @param R 右边界
* @param K 左边跟的boxes[L] 的数量
* @param dp 记忆数组
* @return
*/
private int process(int[] boxes, int L, int R, int K, int[][][] dp) {
// base case：L > R，返回0
if (L > R) return 0;
if (dp[L][R][K] != 0) return dp[L][R][K];
// 优化，前面相同的的都不用试，连成一片
int last = L;
int pre = K; // K要用于记录缓存，所以不能修改，另起一个变量记录
while (last + 1 <= R && boxes[L] == boxes[last + 1]) {
last++;
pre++;
}
// 前pre个跟last一起消掉了，pre清零， 剩下的后面调递归
int res = (pre + 1) * (pre + 1) + process(boxes, last + 1, R, 0, dp);
// 枚举可以跟着前的pre+1个boxes[L]连成一片一起消掉的情况，last + 1是不符合的，跳过
for (int M = last + 2; M <= R; M++) {
// 第一个第一个符合的情况就可以了，后面的会在后续递归连上
if (boxes[L] == boxes[M] && boxes[M - 1] != boxes[L]) {
res = Math.max(res, process(boxes, last + 1, M - 1, 0, dp) + process(boxes, M, R, pre + 1, dp));
}
}
dp[L][R][K] = res;
return res;
}
}
题目三
整型数组arr长度为n(3 <= n <= 10^4)，最初每个数字是<=200的正数且满足如下条件：
1、 0位置的要求：arr[0]<=arr[1]；
2、 n-1位置的要求：arr[n-1]<=arr[n-2]；
3、 中间i位置的要求：arr[i]<=max(arr[i-1],arr[i+1])；
但是在arr有些数字丢失了，比如k位置的数字之前是正数，丢失之后k位置的数字为0。
请你根据上述条件，计算可能有多少种不同的arr可以满足以上条件。
比如 [6,0,9] 只有还原成 [6,9,9]满足全部三个条件，所以返回1种。 [6,9,9] 达标
[ … 0 0]
解法：
从右往左尝试，
f(arr, i, V) 表示来到i位置，期望把它变为V，函数返回满足条件的方法数
如此一来，从N-1位置开始调递归
递归中枚举i-1位置填1~200，继续调递归，
但是i-1位置的数不能乱填，要根据i位置左右两侧的数决定
此时补充一个外部条件简化尝试：S，i与右侧（i+1）数的关系， 0表示小于右边的数，1表示等于右边的数，2表示大于右边的数
此时如果S为0或1，那么i-1就可以随便填
如果S为2，而此时由期望将i位置的数变为V，则i-1位置要填V~200的
这样，在枚举i-1位置的可能性的时候，就不用具体调研左右两侧数的状况，执行根据S进行区分即可
/**
* 整型数组arr长度为n(3 <= n <= 10^4)，最初每个数字是<=200的正数且满足如下条件：
* 1. 0位置的要求：arr[0] <= arr[1]
* 2. n-1位置的要求：arr[n-1] <= arr[n-2]
* 3. 中间i位置的要求：arr[i] <= max(arr[i-1], arr[i+1])
* 但是在arr有些数字丢失了，比如k位置的数字之前是正数，丢失之后k位置的数字为0。
* 请你根据上述条件，计算可能有多少种不同的arr可以满足以上条件。
* 比如 [6,0,9] 只有还原成 [6,9,9]满足全部三个条件，所以返回1种。 [6,9,9] 达标
* [ ...... 0 0]
*
* Created by huangjunyi on 2022/10/21.
*/
public class _41RestoreWays {
public static int ways1(int[] arr) {
int N = arr.length;
if (arr[N - 1] != 0) {
return process1(arr, N - 1, arr[N - 1], 2);
} else {
int ways = 0;
for (int i = 1; i < 201; i++) {
ways += process1(arr, N - 1, i, 2);
}
return ways;
}
}
/**
* i位置的数，把它变成V，S是i位置的数与右边数的关系，返回把数组（从0~i）变成达标数组，有多少种方法
* @param arr 原数组
* @param i 当前下标
* @param V 把i位置的数变为V
* @param S i与右侧（i+1）数的关系， 0表示小于右边的数，1表示等于右边的数，2表示大于右边的数
* @return
*/
private static int process1(int[] arr, int i, int V, int S) {
/*
从右往左递归
记录与前一个数的关系
直到i==0，判断i位置是否符合条件，符合则表示找到一种方法数
每次递归，判断是否符合条件，不为0又不是目标数，提前返回0
*/
// base case：i来到0位置，只有i小于或等于右侧的数，并且是0或者等于V，才算一种有效方法
if (i == 0) return ((S == 0 || S == 1) && (arr[i] == 0 || arr[i] == V)) ? 1 : 0;
// 如果i位置的数没丢掉，又不等于V这个期望值，返回0，无效
if (arr[i] != 0 && arr[i] != V) return 0;
// 遍历i-1位能填的数1~200，递归
int ways = 0;
if (S == 0 || S == 1) {
// i位置的数小于等于i+1位置的数，此时i-1可以随便填
for (int leftValue = 1; i < 201; i++) {
ways += process1(arr, i - 1, leftValue, leftValue < V ? 0 : (leftValue == V ? 1 : 2));
}
} else {
// i位置的数大于i+1位置的数，必须通过i-1填的数补救，否则i就违规了（arr[i] <= max(arr[i-1], arr[i+1])）
for (int leftValue = V; i < 201; i++) {
ways += process1(arr, i - 1, leftValue, leftValue == V ? 1 : 2);
}
}
return ways;
}
/**
* 从递归尝试改成动态规划
* @param arr
* @return
*/
public static int ways2(int[] arr) {
int N = arr.length;
/*
dp[i][V][S]
i位置的数，把它变成V，S是i位置的数与右边数的关系，把数组（从0~i）变成达标数组，有多少种方法
*/
int[][][] dp = new int[N][201][3];
// 根据base case 初始化dp表
// base case：i来到0位置，只有i小于或等于右侧的数，并且是0或者等于V，才算一种有效方法
if (arr[0] != 0) {
dp[0][arr[0]][0] = 1;
dp[0][arr[0]][1] = 1;
} else {
for (int V = 1; V < 201; V++) {
dp[0][V][0] = 1;
dp[0][V][1] = 1;
}
}
for (int i = 1; i < N; i++) {
for (int V = 1; V < 201; V++) {
for (int S = 0; S < 3; S++) {
if (arr[i] != 0 && arr[i] != V) {
// 如果i位置的数没丢掉，又不等于V这个期望值，填0，无效
dp[i][V][S] = 0;
} else {
int ways = 0;
if (S == 0 || S == 1) {
// i位置的数小于等于i+1位置的数，此时i-1随便
for (int leftValue = 1; i < 201; i++) {
ways += dp[i - 1][leftValue][leftValue < V ? 0 : (leftValue == V ? 1 : 2)];
}
} else {
// i位置的数大于i+1位置的数，必须通过i-1填的数补救，否则i就违规了（arr[i] <= max(arr[i-1], arr[i+1])）
for (int leftValue = V; i < 201; i++) {
ways += dp[i - 1][leftValue][leftValue == V ? 1 : 2];
}
}
dp[i][V][S] = ways;
}
}
}
}
// 根据顶层递归，确定返回值
if (arr[N - 1] != 0) {
return dp[N - 1][arr[N - 1]][2];
} else {
int ways = 0;
for (int i = 1; i < 201; i++) {
ways += dp[N - 1][i][2];
}
return ways;
}
}
/**
* 动态规划枚举行为优化
* @param arr
* @return
*/
public static int ways3(int[] arr) {
int N = arr.length;
int[][][] dp = new int[N][201][3];
if (arr[0] != 0) {
dp[0][arr[0]][0] = 1;
dp[0][arr[0]][1] = 1;
} else {
for (int V = 1; V < 201; V++) {
dp[0][V][0] = 1;
dp[0][V][1] = 1;
}
}
/*
preSum用于简化枚举行为
preSum[V][s]
表示原先递归从0~V位置，与右侧关系为s，的前缀和
比如preSum[60][0]
表示i为0~60，s为0，所有方法数的累加和
*/
int[][] preSum = new int[201][3];
for (int v = 1; v < 201; v++) {
for (int s = 0; s < 3; s++) {
preSum[v][s] = preSum[v - 1][s] + dp[0][v][s];
}
}
for (int i = 1; i < N; i++) {
for (int V = 1; V < 201; V++) {
for (int S = 0; S < 3; S++) {
if (arr[i] != 0 && arr[i] != V) {
dp[i][V][S] = 0;
} else {
// 通过preSum简化枚举
int ways = 0;
if (S == 0 || S == 1) {
ways += preSum[V - 1][0] + dp[i - 1][V][1] + preSum[200][0] - preSum[V][0];
} else {
ways += dp[i - 1][V][1] + preSum[200][2] - preSum[V][2];
}
dp[i][V][S] = ways;
}
}
}
// 加工preSum
for (int v = 1; v < 201; v++) {
for (int s = 0; s < 3; s++) {
preSum[v][s] = preSum[v - 1][s] + dp[i][v][s];
}
}
}
if (arr[N - 1] != 0) {
return dp[N - 1][arr[N - 1]][2];
} else {
int ways = 0;
for (int i = 1; i < 201; i++) {
ways += dp[N - 1][i][2];
}
return ways;
}
}
}