class076 区间dp-上【算法】

算法讲解076【必备】区间dp-上

code1 1312. 让字符串成为回文串的最少插入次数

// 让字符串成为回文串的最少插入次数
// 给你一个字符串 s
// 每一次操作你都可以在字符串的任意位置插入任意字符
// 请你返回让s成为回文串的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

int f(char[] s,l,r)
lr,一个字符
返回0，不用插入字符就是回文串
l+1r,两个字符
相同，返回0
不同，返回1
s[l]==s[r]
返回f(s,l+1,r-1)
其余
返回min(f(s,l,r-1),f(s,l+1,r))+1

package class076;// 让字符串成为回文串的最少插入次数
// 给你一个字符串 s
// 每一次操作你都可以在字符串的任意位置插入任意字符
// 请你返回让s成为回文串的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
public class Code01_MinimumInsertionToPalindrome {// 暴力尝试public static int minInsertions1(String str) {char[] s = str.toCharArray();int n = s.length;return f1(s, 0, n - 1);}// s[l....r]这个范围上的字符串，整体都变成回文串// 返回至少插入几个字符public static int f1(char[] s, int l, int r) {// l <= rif (l == r) {return 0;}if (l + 1 == r) {return s[l] == s[r] ? 0 : 1;}// l...r不只两个字符if (s[l] == s[r]) {return f1(s, l + 1, r - 1);} else {return Math.min(f1(s, l, r - 1), f1(s, l + 1, r)) + 1;}}// 记忆化搜索public static int minInsertions2(String str) {char[] s = str.toCharArray();int n = s.length;int[][] dp = new int[n][n];for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {dp[i][j] = -1;}}return f2(s, 0, n - 1, dp);}public static int f2(char[] s, int l, int r, int[][] dp) {if (dp[l][r] != -1) {return dp[l][r];}int ans;if (l == r) {ans = 0;} else if (l + 1 == r) {ans = s[l] == s[l + 1] ? 0 : 1;} else {if (s[l] == s[r]) {ans = f2(s, l + 1, r - 1, dp);} else {ans = Math.min(f2(s, l, r - 1, dp), f2(s, l + 1, r, dp)) + 1;}}dp[l][r] = ans;return ans;}// 严格位置依赖的动态规划public static int minInsertions3(String str) {char[] s = str.toCharArray();int n = s.length;int[][] dp = new int[n][n];for (int l = 0; l < n - 1; l++) {dp[l][l + 1] = s[l] == s[l + 1] ? 0 : 1;}for (int l = n - 3; l >= 0; l--) {for (int r = l + 2; r < n; r++) {if (s[l] == s[r]) {dp[l][r] = dp[l + 1][r - 1];} else {dp[l][r] = Math.min(dp[l][r - 1], dp[l + 1][r]) + 1;}}}return dp[0][n - 1];}// 空间压缩// 本题有关空间压缩的实现，可以参考讲解067，题目4，最长回文子序列问题的讲解// 这两个题空间压缩写法高度相似// 因为之前的课多次讲过空间压缩的内容，所以这里不再赘述public static int minInsertions4(String str) {char[] s = str.toCharArray();int n = s.length;if (n < 2) {return 0;}int[] dp = new int[n];dp[n - 1] = s[n - 2] == s[n - 1] ? 0 : 1;for (int l = n - 3, leftDown, backUp; l >= 0; l--) {leftDown = dp[l + 1];dp[l + 1] = s[l] == s[l + 1] ? 0 : 1;for (int r = l + 2; r < n; r++) {backUp = dp[r];if (s[l] == s[r]) {dp[r] = leftDown;} else {dp[r] = Math.min(dp[r - 1], dp[r]) + 1;}leftDown = backUp;}}return dp[n - 1];}}

code2 486. 预测赢家

// 预测赢家
// 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏
// 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手
// 开始时，两个玩家的初始分值都是 0
// 每一回合，玩家从数组的任意一端取一个数字
// 取到的数字将会从数组中移除，数组长度减1
// 玩家选中的数字将会加到他的得分上
// 当数组中没有剩余数字可取时游戏结束
// 如果玩家 1 能成为赢家，返回 true
// 如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true
// 你可以假设每个玩家的玩法都会使他的分数最大化
// 测试链接 : https://leetcode.cn/problems/predict-the-winner/

int f1(int[] nums,int l,int r)
lr：nums[l]
l+1r：max(nums[l],nums[r])
拿走l位置的数：nums[l]+min(f(nums,l+2,r),f(nums,l+1,r-1))
拿走r位置的数：nums[r]+min(f(nums,l+1,r-1),f(nums,l,r-2))
max()
为什么min，因为玩家2也是最优的选择，所以玩家1就是剩余范围较差的选择

package class076;// 预测赢家
// 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏
// 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手
// 开始时，两个玩家的初始分值都是 0
// 每一回合，玩家从数组的任意一端取一个数字
// 取到的数字将会从数组中移除，数组长度减1
// 玩家选中的数字将会加到他的得分上
// 当数组中没有剩余数字可取时游戏结束
// 如果玩家 1 能成为赢家，返回 true
// 如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true
// 你可以假设每个玩家的玩法都会使他的分数最大化
// 测试链接 : https://leetcode.cn/problems/predict-the-winner/
public class Code02_PredictTheWinner {// 暴力尝试public static boolean predictTheWinner1(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}int n = nums.length;int first = f1(nums, 0, n - 1);int second = sum - first;return first >= second;}// nums[l...r]范围上的数字进行游戏，轮到玩家1// 返回玩家1最终能获得多少分数，玩家1和玩家2都绝顶聪明public static int f1(int[] nums, int l, int r) {if (l == r) {return nums[l];}if (l == r - 1) {return Math.max(nums[l], nums[r]);}// l....r 不只两个数// 可能性1 ：玩家1拿走nums[l] l+1...rint p1 = nums[l] + Math.min(f1(nums, l + 2, r), f1(nums, l + 1, r - 1));// 可能性2 ：玩家1拿走nums[r] l...r-1int p2 = nums[r] + Math.min(f1(nums, l + 1, r - 1), f1(nums, l, r - 2));return Math.max(p1, p2);}// 记忆化搜索public static boolean predictTheWinner2(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}int n = nums.length;int[][] dp = new int[n][n];for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {dp[i][j] = -1;}}int first = f2(nums, 0, n - 1, dp);int second = sum - first;return first >= second;}public static int f2(int[] nums, int l, int r, int[][] dp) {if (dp[l][r] != -1) {return dp[l][r];}int ans;if (l == r) {ans = nums[l];} else if (l == r - 1) {ans = Math.max(nums[l], nums[r]);} else {int p1 = nums[l] + Math.min(f2(nums, l + 2, r, dp), f2(nums, l + 1, r - 1, dp));int p2 = nums[r] + Math.min(f2(nums, l + 1, r - 1, dp), f2(nums, l, r - 2, dp));ans = Math.max(p1, p2);}dp[l][r] = ans;return ans;}// 严格位置依赖的动态规划public static boolean predictTheWinner3(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}int n = nums.length;int[][] dp = new int[n][n];for (int i = 0; i < n - 1; i++) {dp[i][i] = nums[i];dp[i][i + 1] = Math.max(nums[i], nums[i + 1]);}dp[n - 1][n - 1] = nums[n - 1];for (int l = n - 3; l >= 0; l--) {for (int r = l + 2; r < n; r++) {dp[l][r] = Math.max(nums[l] + Math.min(dp[l + 2][r], dp[l + 1][r - 1]),nums[r] + Math.min(dp[l + 1][r - 1], dp[l][r - 2]));}}int first = dp[0][n - 1];int second = sum - first;return first >= second;}}

code3 1039. 多边形三角剖分的最低得分

// 多边形三角剖分的最低得分
// 你有一个凸的 n 边形，其每个顶点都有一个整数值
// 给定一个整数数组values，其中values[i]是第i个顶点的值(顺时针顺序)
// 假设将多边形 剖分 为 n - 2 个三角形
// 对于每个三角形，该三角形的值是顶点标记的乘积
// 三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和
// 返回 多边形进行三角剖分后可以得到的最低分
// 测试链接 : https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/

f(int[] arr,int l,int r)
∑{(0,i,5)+f(arr,l,i)+f(arr,i,r)} 1<=i<=n-1

package class076;// 多边形三角剖分的最低得分
// 你有一个凸的 n 边形，其每个顶点都有一个整数值
// 给定一个整数数组values，其中values[i]是第i个顶点的值(顺时针顺序)
// 假设将多边形 剖分 为 n - 2 个三角形
// 对于每个三角形，该三角形的值是顶点标记的乘积
// 三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和
// 返回 多边形进行三角剖分后可以得到的最低分
// 测试链接 : https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/
public class Code03_MinimumScoreTriangulationOfPolygon {// 记忆化搜索public static int minScoreTriangulation1(int[] arr) {int n = arr.length;int[][] dp = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dp[i][j] = -1;}}return f(arr, 0, n - 1, dp);}public static int f(int[] arr, int l, int r, int[][] dp) {if (dp[l][r] != -1) {return dp[l][r];}int ans = Integer.MAX_VALUE;if (l == r || l == r - 1) {ans = 0;} else {// l....r >=3// 0..1..2..3..4...5for (int m = l + 1; m < r; m++) {// l m rans = Math.min(ans, f(arr, l, m, dp) + f(arr, m, r, dp) + arr[l] * arr[m] * arr[r]);}}dp[l][r] = ans;return ans;}// 严格位置依赖的动态规划public static int minScoreTriangulation2(int[] arr) {int n = arr.length;int[][] dp = new int[n][n];for (int l = n - 3; l >= 0; l--) {for (int r = l + 2; r < n; r++) {dp[l][r] = Integer.MAX_VALUE;for (int m = l + 1; m < r; m++) {dp[l][r] = Math.min(dp[l][r], dp[l][m] + dp[m][r] + arr[l] * arr[m] * arr[r]);}}}return dp[0][n - 1];}}

code4 1547. 切棍子的最小成本

// 切棍子的最小成本
// 有一根长度为n个单位的木棍，棍上从0到n标记了若干位置
// 给你一个整数数组cuts，其中cuts[i]表示你需要将棍子切开的位置
// 你可以按顺序完成切割，也可以根据需要更改切割的顺序
// 每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和
// 对棍子进行切割将会把一根木棍分成两根较小的木棍
// 这两根木棍的长度和就是切割前木棍的长度
// 返回切棍子的最小总成本
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/

arr数组：0,cuts[],n排序
f(arr,l,r)
就是当前代价arr[r+1]-arr[l-1]
+f(arr,l,m-1)+f(arr,m+1,r)
枚举m

package class076;import java.util.Arrays;// 切棍子的最小成本
// 有一根长度为n个单位的木棍，棍上从0到n标记了若干位置
// 给你一个整数数组cuts，其中cuts[i]表示你需要将棍子切开的位置
// 你可以按顺序完成切割，也可以根据需要更改切割的顺序
// 每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和
// 对棍子进行切割将会把一根木棍分成两根较小的木棍
// 这两根木棍的长度和就是切割前木棍的长度
// 返回切棍子的最小总成本
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/
public class Code04_MinimumCostToCutAStick {// 记忆化搜索public static int minCost1(int n, int[] cuts) {int m = cuts.length;Arrays.sort(cuts);int[] arr = new int[m + 2];arr[0] = 0;for (int i = 1; i <= m; ++i) {arr[i] = cuts[i - 1];}arr[m + 1] = n;int[][] dp = new int[m + 2][m + 2];for (int i = 1; i <= m; i++) {for (int j = 1; j <= m; j++) {dp[i][j] = -1;}}return f(arr, 1, m, dp);}// 切点[l....r]，决定一个顺序// 让切点都切完，总代价最小public static int f(int[] arr, int l, int r, int[][] dp) {if (l > r) {return 0;}if (l == r) {return arr[r + 1] - arr[l - 1];}if (dp[l][r] != -1) {return dp[l][r];}int ans = Integer.MAX_VALUE;for (int k = l; k <= r; k++) {ans = Math.min(ans, f(arr, l, k - 1, dp) + f(arr, k + 1, r, dp));}ans += arr[r + 1] - arr[l - 1];dp[l][r] = ans;return ans;}// 严格位置依赖的动态规划public static int minCost2(int n, int[] cuts) {int m = cuts.length;Arrays.sort(cuts);int[] arr = new int[m + 2];arr[0] = 0;for (int i = 1; i <= m; ++i) {arr[i] = cuts[i - 1];}arr[m + 1] = n;int[][] dp = new int[m + 2][m + 2];for (int i = 1; i <= m; i++) {dp[i][i] = arr[i + 1] - arr[i - 1];}for (int l = m - 1, next; l >= 1; l--) {for (int r = l + 1; r <= m; r++) {next = Integer.MAX_VALUE;for (int k = l; k <= r; k++) {next = Math.min(next, dp[l][k - 1] + dp[k + 1][r]);}dp[l][r] = arr[r + 1] - arr[l - 1] + next;}}return dp[1][m];}}

code5 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 的气球
// 求所能获得硬币的最大数量
// 测试链接 : https://leetcode.cn/problems/burst-balloons/

尝试先打爆不行
尝试最后打爆

[l-1] [r+1]的位置没被打爆
int f(int[] arr, int l, int r)
遍历m
f(arr,l,m-1)+f(arr,m+1,r)
最后加上打爆m的得分：arr[l-1]*arr[m]*arr[r+1]
因为[l,r]位置上只剩下m位置了

package class076;// 戳气球
// 有 n 个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中
// 现在要求你戳破所有的气球。戳破第 i 个气球
// 你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币
// 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号
// 如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球
// 求所能获得硬币的最大数量
// 测试链接 : https://leetcode.cn/problems/burst-balloons/
public class Code05_BurstBalloons {// 记忆化搜索public static int maxCoins1(int[] nums) {int n = nums.length;// a b c d e// 1 a b c d e 1int[] arr = new int[n + 2];arr[0] = 1;arr[n + 1] = 1;for (int i = 0; i < n; i++) {arr[i + 1] = nums[i];}int[][] dp = new int[n + 2][n + 2];for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {dp[i][j] = -1;}}return f(arr, 1, n, dp);}// arr[l...r]这些气球决定一个顺序，获得最大得分返回！// 一定有 : arr[l-1]一定没爆！// 一定有 : arr[r+1]一定没爆！// 尝试每个气球最后打爆public static int f(int[] arr, int l, int r, int[][] dp) {if (dp[l][r] != -1) {return dp[l][r];}int ans;if (l == r) {ans = arr[l - 1] * arr[l] * arr[r + 1];} else {// l   ....r// l +1 +2 .. rans = Math.max(arr[l - 1] * arr[l] * arr[r + 1] + f(arr, l + 1, r, dp), // l位置的气球最后打爆arr[l - 1] * arr[r] * arr[r + 1] + f(arr, l, r - 1, dp));// r位置的气球最后打爆for (int k = l + 1; k < r; k++) {// k位置的气球最后打爆// l...k-1  k  k+1...rans = Math.max(ans, arr[l - 1] * arr[k] * arr[r + 1] + f(arr, l, k - 1, dp) + f(arr, k + 1, r, dp));}}dp[l][r] = ans;return ans;}// 严格位置依赖的动态规划public static int maxCoins2(int[] nums) {int n = nums.length;int[] arr = new int[n + 2];arr[0] = 1;arr[n + 1] = 1;for (int i = 0; i < n; i++) {arr[i + 1] = nums[i];}int[][] dp = new int[n + 2][n + 2];for (int i = 1; i <= n; i++) {dp[i][i] = arr[i - 1] * arr[i] * arr[i + 1];}for (int l = n, ans; l >= 1; l--) {for (int r = l + 1; r <= n; r++) {ans = Math.max(arr[l - 1] * arr[l] * arr[r + 1] + dp[l + 1][r],arr[l - 1] * arr[r] * arr[r + 1] + dp[l][r - 1]);for (int k = l + 1; k < r; k++) {ans = Math.max(ans, arr[l - 1] * arr[k] * arr[r + 1] + dp[l][k - 1] + dp[k + 1][r]);}dp[l][r] = ans;}}return dp[1][n];}}

code6 面试题 08.14. 布尔运算

// 布尔运算
// 给定一个布尔表达式和一个期望的布尔结果 result
// 布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成
// 布尔表达式一定是正确的，不需要检查有效性
// 但是其中没有任何括号来表示优先级
// 你可以随意添加括号来改变逻辑优先级
// 目的是让表达式能够最终得出result的结果
// 返回最终得出result有多少种不同的逻辑计算顺序
// 测试链接 : https://leetcode.cn/problems/boolean-evaluation-lcci/

枚举最后运算的符号

以结果是True，举例：
f(char[] s,int l,int r)
s[k]是&
f(s,l,k-1)是True的结果数乘以f(s,k+1,r)是True的结果数
s[k]是^
f(s,l,k-1)是F的结果数乘以f(s,k+1,r)是T的结果数+f(s,l,k-1)是T的结果数乘以f(s,k+1,r)是F的结果数
s[k]是|
f(s,l,k-1)是T的结果数乘以f(s,k+1,r)是T的结果数+f(s,l,k-1)是T的结果数乘以f(s,k+1,r)是F的结果数+f(s,l,k-1)是F的结果数乘以f(s,k+1,r)是T的结果数

package class076;// 布尔运算
// 给定一个布尔表达式和一个期望的布尔结果 result
// 布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成
// 布尔表达式一定是正确的，不需要检查有效性
// 但是其中没有任何括号来表示优先级
// 你可以随意添加括号来改变逻辑优先级
// 目的是让表达式能够最终得出result的结果
// 返回最终得出result有多少种不同的逻辑计算顺序
// 测试链接 : https://leetcode.cn/problems/boolean-evaluation-lcci/
public class Code06_BooleanEvaluation {// 记忆化搜索public static int countEval(String str, int result) {char[] s = str.toCharArray();int n = s.length;int[][][] dp = new int[n][n][];int[] ft = f(s, 0, n - 1, dp);return ft[result];}// s[l...r]是表达式的一部分，且一定符合范式// 0/1  逻  0/1   逻       0/1//  l  l+1  l+2  l+3........r// s[l...r]  0 : ?//           1 : ?// ans : int[2] ans[0] = false方法数 ans[0] = true方法数public static int[] f(char[] s, int l, int r, int[][][] dp) {if (dp[l][r] != null) {return dp[l][r];}int f = 0;int t = 0;if (l == r) {// 只剩一个字符，0/1f = s[l] == '0' ? 1 : 0;t = s[l] == '1' ? 1 : 0;} else {int[] tmp;for (int k = l + 1, a, b, c, d; k < r; k += 2) {// l ... r// 枚举每一个逻辑符号最后执行 k = l+1 ... r-1  k+=2tmp = f(s, l, k - 1, dp);a = tmp[0];b = tmp[1];tmp = f(s, k + 1, r, dp);c = tmp[0];d = tmp[1];if (s[k] == '&') {f += a * c + a * d + b * c;t += b * d;} else if (s[k] == '|') {f += a * c;t += a * d + b * c + b * d;} else {f += a * c + b * d;t += a * d + b * c;}}}int[] ft = new int[] { f, t };dp[l][r] = ft;return ft;}}

2023-11-20 21:29:42