第六章：动态规划
一、基本动态规划：一维
1、爬楼梯
问题：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
1 package LeetCode.test6_dongtaiguihua; 2 3 /** 4 * 思路：第i阶可以从第i-1或i-2阶到达 dp[i] = dp[i-1] + dp[i-2] 5 * 解释：到达第i阶 = （到达第i-2阶的方法数 + 2步）||（到达第i-1阶的方法数 + 1步） 6 * -> 走到第i阶的方法数即为走到第i-1阶的方法数加上走到第i-2阶的方法数 7 */ 8 public class ques_70_爬楼梯 { 9 public int climbStairs(int n) { 10 if (n <= 2) { 11 return n; 12 } 13 int[] dp = new int[n + 1]; 14 dp[1] = 1; 15 dp[2] = 2; 16 for (int i = 3; i <= n; i++) { 17 dp[i] = dp[i - 1] + dp[i - 2]; 18 } 19 return dp[n]; 20 } 21 } 22 23 class Test_70 { 24 public static void main(String[] args) { 25 int n = 3; 26 ques_70_爬楼梯 s = new ques_70_爬楼梯(); 27 System.out.println(s.climbStairs(n)); 28 } 29 }
2、打家劫舍
问题：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 * 思路：dp[i] = max(dp[i-1],nums[i-1] + dp[i-2]) 7 * dp[i-1] -> 不抢 nums[i-1] + dp[i-2] -> 抢 8 */ 9 public class ques_198_打家劫舍 { 10 public int rob(int[] nums) { 11 if (nums.length == 0){ 12 return 0; 13 } 14 if (nums.length == 1){ 15 return nums[0]; 16 } 17 int[] dp = new int[nums.length + 1]; 18 dp[1] = nums[0]; 19 dp[2] = Math.max(nums[0], nums[1]); 20 for (int i = 2; i <= nums.length; i++) { 21 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]); 22 } 23 Arrays.sort(dp); 24 return dp[nums.length]; 25 } 26 } 27 28 class Test_198 { 29 public static void main(String[] args) { 30 // int[] nums = {2, 7, 9, 3, 1}; 31 // int[] nums = {2}; 32 // int[] nums = {2,7}; 33 int[] nums = {}; 34 ques_198_打家劫舍 s = new ques_198_打家劫舍(); 35 System.out.println(s.rob(nums)); 36 } 37 }
3、等差数列划分
问题：
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
输入：nums = [1]
输出：0
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 * 思路：dp[i]表示以nums[i]为结尾的等差递增子区间的个数。 7 * dp[2] = 1 [0, 1, 2] 8 * dp[3] = dp[2] + 1 = 2 [0, 1, 2, 3] [1, 2, 3] 9 * dp[4] = dp[3] + 1 = 3 [0, 1, 2, 3, 4] [1, 2, 3, 4] [2, 3, 4] 10 * 因为递增子区间不一定以最后一个元素为结尾，可以是任意一个元素结尾，因此需要返回dp数组累加的结果。 11 */ 12 public class ques_413_等差数列划分 { 13 public int numberOfArithmeticSlices(int[] nums) { 14 if (nums.length < 3) { 15 return 0; 16 } 17 int[] dp = new int[nums.length]; 18 for (int i = 2; i < nums.length; i++) { 19 if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) { 20 dp[i] = dp[i - 1] + 1; 21 } 22 } 23 System.out.println(Arrays.toString(dp)); 24 return Arrays.stream(dp).sum(); 25 } 26 } 27 28 class Test_413 { 29 public static void main(String[] args) { 30 // int[] nums = {1, 2, 3, 4}; 31 // int[] nums = {1, 1, 2, 3, 4, 6}; 32 int[] nums = {1, 2, 3, 4, 5}; 33 ques_413_等差数列划分 s = new ques_413_等差数列划分(); 34 System.out.println(s.numberOfArithmeticSlices(nums)); 35 } 36 }
二、基本动态规划：二维
4、最小路径和
问题：
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
1 package LeetCode.test6_dongtaiguihua; 2 3 public class ques_64_最小路径和 { 4 public int minPathSum(int[][] grid) { 5 int[][] dp = new int[grid.length][grid[0].length]; 6 for (int i = 0; i < grid.length; i++) { 7 for (int j = 0; j < grid[0].length; j++) { 8 if (i == 0 && j == 0) { 9 dp[0][0] = grid[0][0]; 10 } else if (i == 0) { 11 dp[0][j] = dp[0][j - 1] + grid[0][j]; 12 } else if (j == 0) { 13 dp[i][0] = dp[i - 1][0] + grid[i][0]; 14 } else { 15 dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]; 16 } 17 } 18 } 19 return dp[grid.length - 1][grid[0].length - 1]; 20 } 21 22 public int minPathSum2(int[][] grid) { 23 /* 24 * 空间压缩:对于第i行，在遍历到第j列的时候，因为第j-1列已经更新过了，所以dp[j-1]代表dp[i][j-1]的值; 25 * 而dp[j]待更新，当前存储的值是在第i-1行的时候计算的，所以代表dp[i-1][j]的值。 26 * eg: 1 ,3 ,1 i = 2时 dp[2] = min(dp[2],dp[1]) + grid[2][2] dp -> [6, 8, 7] 27 * 1 ,5 ,1 min中的dp[2] -> 1 ,3 ,1 这部分的dp[2] 28 * 4 ,2 ,1 1 ,5 ,1 29 * min中的dp[1] -> 1 ,3 这部分的dp[1] 30 * 1 ,5 31 * 4 ,2 32 */ 33 int[] dp = new int[grid[0].length]; 34 for (int i = 0; i < grid.length; i++) { 35 for (int j = 0; j < grid[0].length; j++) { 36 if (i == 0 && j == 0) { 37 dp[j] = grid[i][j]; 38 } else if (i == 0) { 39 dp[j] = dp[j - 1] + grid[i][j]; 40 } else if (j == 0) { 41 dp[j] = dp[j] + grid[i][j]; 42 } else { 43 dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]; 44 } 45 } 46 } 47 return dp[grid[0].length - 1]; 48 } 49 } 50 51 class Test_64 { 52 public static void main(String[] args) { 53 int[][] grid = {{1, 3, 1}, 54 {1, 5, 1}, 55 {4, 2, 1}}; 56 ques_64_最小路径和 s = new ques_64_最小路径和(); 57 System.out.println(s.minPathSum(grid)); 58 System.out.println(s.minPathSum2(grid)); 59 } 60 }
5、01矩阵
问题：
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 思路：从左上到右下进行一次动态搜索，再从右下到左上进行一次动态搜索。 7 */ 8 public class ques_542_01矩阵 { 9 public int[][] updateMatrix(int[][] mat) { 10 int m = mat.length; 11 int n = mat[0].length; 12 int[][] dp = new int[m][n]; 13 for (int i = 0; i < m; i++) { 14 Arrays.fill(dp[i], Integer.MAX_VALUE - 1); 15 } 16 17 for (int i = 0; i < m; i++) { 18 for (int j = 0; j < n; j++) { 19 if (mat[i][j] == 0) { 20 dp[i][j] = 0; 21 } else { 22 if (i > 0) { 23 dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1); 24 } 25 if (j > 0) { 26 dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1); 27 } 28 } 29 } 30 } 31 32 for (int i = m - 1; i >= 0; i--) { 33 for (int j = n - 1; j >= 0; j--) { 34 if (mat[i][j] != 0) { 35 if (i < m - 1) { 36 dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1); 37 } 38 if (j < n - 1) { 39 dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1); 40 } 41 } 42 } 43 } 44 return dp; 45 } 46 } 47 48 class Test_542 { 49 public static void main(String[] args) { 50 // int[][] mat = {{0, 0, 0}, 51 // {0, 1, 0}, 52 // {1, 1, 1}}; 53 int[][] mat = {{1, 1, 0, 0, 1, 0, 0, 1, 1, 0}, 54 {1, 0, 0, 1, 0, 1, 1, 1, 1, 1}, 55 {1, 1, 1, 0, 0, 1, 1, 1, 1, 0}, 56 {0, 1, 1, 1, 0, 1, 1, 1, 1, 1}, 57 {0, 0, 1, 1, 1, 1, 1, 1, 1, 0}, 58 {1, 1, 1, 1, 1, 1, 0, 1, 1, 1}, 59 {0, 1, 1, 1, 1, 1, 1, 0, 0, 1}, 60 {1, 1, 1, 1, 1, 0, 0, 1, 1, 1}, 61 {0, 1, 0, 1, 1, 0, 1, 1, 1, 1}, 62 {1, 1, 1, 0, 1, 0, 1, 1, 1, 1}}; 63 ques_542_01矩阵 s = new ques_542_01矩阵(); 64 System.out.println(Arrays.deepToString(s.updateMatrix(mat))); 65 } 66 }
6、最大正方形
问题：
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
1 package LeetCode.test6_dongtaiguihua; 2 3 4 /** 5 * 思路：假设dp[i][j] = k的平方 ，其充分条件为 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 的值必须 6 都不小于 (k ? 1)的平方 ，否则 (i, j) 位置不可以构成一个边长为 k 的正方形。同理，如果这三个值中的 7 的最小值为 k ? 1，则 (i, j) 位置一定且最大可以构成一个边长为 k 的正方形。 8 */ 9 public class ques_221_最大正方形 { 10 public int maximalSquare(char[][] matrix) { 11 int m = matrix.length; 12 int n = matrix[0].length; 13 int[][] dp = new int[m + 1][n + 1]; 14 int max_side = 0; 15 16 for (int i = 1; i <= m; i++) { 17 for (int j = 1; j <= n; j++) { 18 if (matrix[i - 1][j - 1] == '1') { 19 dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1; 20 } 21 max_side = Math.max(max_side, dp[i][j]); 22 } 23 } 24 /* 25 [0, 0, 0, 0, 0, 0] 26 [0, 1, 0, 1, 0, 0] 27 [0, 1, 0, 1, 1, 1] 28 [0, 1, 1, 1, 2, 2] 29 [0, 1, 0, 0, 1, 0]0 30 注意：只有matrix[i][j]=1的时候，对应的dp值才有可能变。 31 */ 32 return max_side * max_side; 33 } 34 } 35 36 class Test_221 { 37 public static void main(String[] args) { 38 char[][] matrix = {{'1', '0', '1', '0', '0'}, 39 {'1', '0', '1', '1', '1'}, 40 {'1', '1', '1', '1', '1'}, 41 {'1', '0', '0', '1', '0'}}; 42 // char[][] matrix = {{'1', '0', '0', '0', '0'}, 43 // {'0', '0', '0', '0', '0'}, 44 // {'0', '0', '0', '0', '0'}, 45 // {'0', '0', '0', '0', '0'}}; 46 ques_221_最大正方形 s = new ques_221_最大正方形(); 47 System.out.println(s.maximalSquare(matrix)); 48 } 49 }
三、分割类型题
7、完全平方数
问题：
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 * 思路：位置i只依赖i-k的平方的位置，如i-1、i-4、i-9等等，才能满足完全平方分割 7 * 的条件，因此dp[i]可以取的最小值即为1+min(dp[i-1], dp[i-4], dp[i-9] ···)。 8 */ 9 public class ques_279_完全平方数 { 10 public int numSquares(int n) { 11 int[] dp = new int[n + 1]; 12 Arrays.fill(dp, Integer.MAX_VALUE); 13 dp[0] = 0; 14 for (int i = 1; i <= n; i++) { 15 for (int j = 1; j * j <= i; j++) { 16 dp[i] = Math.min(dp[i], dp[i - j * j] + 1); 17 } 18 } 19 System.out.println(Arrays.toString(dp)); 20 21 return dp[n]; 22 } 23 } 24 25 class Test_279 { 26 public static void main(String[] args) { 27 int n = 12; 28 ques_279_完全平方数 s = new ques_279_完全平方数(); 29 System.out.println(s.numSquares(n)); 30 } 31 }
8、解码方法
问题：
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 public class ques_91_解码方法 { 6 public int numDecodings(String s) { 7 int m = s.length(); 8 if (s.charAt(0)=='0'){ 9 return 0; 10 } 11 int[] dp = new int[m + 1]; 12 Arrays.fill(dp, 1); 13 dp[1] = 1; 14 for (int i = 2; i <= m; i++) { 15 int num = Integer.parseInt(s.charAt(i - 2) + String.valueOf(s.charAt(i - 1))); 16 if ((s.charAt(i - 1) - '0' == 0 && num > 26) || num==0) { 17 dp[i] = 0; 18 }else if (s.charAt(i - 1) - '0' == 0 && num <= 26) { 19 dp[i] = dp[i - 2]; 20 } 21 else if ((s.charAt(i - 2) - '0' == 0) || num > 26) { 22 dp[i] = dp[i - 1]; 23 } else { 24 dp[i] = dp[i - 1] + dp[i - 2]; 25 } 26 } 27 return dp[m]; 28 } 29 } 30 31 class Test_91 { 32 public static void main(String[] args) { 33 String s = "10011"; 34 ques_91_解码方法 q = new ques_91_解码方法(); 35 System.out.println(q.numDecodings(s)); 36 } 37 }
9、单词拆分
问题：
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 import java.util.List; 5 6 /** 7 思路：s = "applepenapple"; wordDict = {"apple", "pen"}; 8 dp[5] = dp[5]||dp[0] = true; 9 dp[8] = dp[8]||dp[5] = true; 10 如果不匹配，则dp[8] = dp[8]||dp[?] = false,后面的则都为false 11 dp[13] = dp[13]||dp[8] = true; 12 */ 13 public class ques_139_单词拆分 { 14 public boolean wordBreak(String s, ListwordDict) { 15 int m = s.length(); 16 boolean[] dp = new boolean[m + 1]; 17 dp[0] = true; 18 for (int i = 1; i <= m; i++) { 19 for (String word : wordDict) { 20 int len = word.length(); 21 if (i >= len && s.substring(i - len, i).equals(word)) { 22 dp[i] = dp[i] || dp[i - len]; 23 } 24 } 25 } 26 return dp[m]; 27 } 28 } 29 30 31 class Test_139 { 32 public static void main(String[] args) { 33 String s = "leetcode"; 34 String[] word = {"leet", "code"}; 35 List wordDict = Arrays.asList(word); 36 ques_139_单词拆分 p = new ques_139_单词拆分(); 37 System.out.println(p.wordBreak(s, wordDict)); 38 } 39 }
四、子序列问题
10、最长递增子序列
问题：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
1 package LeetCode.test6_dongtaiguihua; 2 3 4 import java.util.Arrays; 5 6 public class ques_300_最长递增子序列 { 7 public int lengthOfLIS(int[] nums) { 8 int m = nums.length; 9 int[] dp = new int[m]; 10 Arrays.fill(dp, 1); 11 int max_length = 0; 12 for (int i = 0; i < m; i++) { 13 for (int j = 0; j < i; j++) { 14 if (nums[j] < nums[i]) { 15 dp[i] = Math.max(dp[i], dp[j] + 1); 16 } 17 } 18 max_length = Math.max(max_length, dp[i]); 19 } 20 return max_length; 21 } 22 } 23 24 class Test_300 { 25 public static void main(String[] args) { 26 int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; 27 ques_300_最长递增子序列 s = new ques_300_最长递增子序列(); 28 System.out.println(s.lengthOfLIS(nums)); 29 } 30 }
11、最长公共子序列
问题：
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
1 package LeetCode.test6_dongtaiguihua; 2 3 public class ques_1143_最长公共子序列 { 4 public int longestCommonSubsequence(String text1, String text2) { 5 int m = text1.length(); 6 int n = text2.length(); 7 int[][] dp = new int[m + 1][n + 1]; 8 for (int i = 1; i <= m; i++) { 9 for (int j = 1; j <= n; j++) { 10 if (text1.charAt(i - 1) == text2.charAt(j - 1)) { 11 dp[i][j] = dp[i - 1][j - 1] + 1; 12 } else { 13 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); 14 } 15 } 16 } 17 return dp[m][n]; 18 } 19 } 20 21 class Test_1143 { 22 public static void main(String[] args) { 23 String text1 = "abcde"; 24 String text2 = "ace"; 25 ques_1143_最长公共子序列 s = new ques_1143_最长公共子序列(); 26 System.out.println(s.longestCommonSubsequence(text1, text2)); 27 } 28 }
五、 背包问题
Demo1、01背包问题
1 package LeetCode.test6_dongtaiguihua; 2 3 /* 4 口诀：0-1背包对物品的迭代放在外层，里层的体积或价值逆向遍历； 5 完全背包对物品的迭代放在里层，外层的体积或价值正向遍历。 6 */ 7 8 /** 9 * 思路： dp[i][j]表示前i件物品体积不超过j的情况下能达到的最大价值。 10 * 在当前背包总容量为j的情况下，如果不将物品i放入背包，那么dp[i][j]=dp[i-1][j]， 11 * 即前i个物品的最大价值等于只取前i-1个物品时的最大价值；如果将物品i放入背包， 12 * 假设第i件物品体积为w，价值为v，那么得到dp[i][j] = dp[i-1][j-w] + v。 13 */ 14 public class demo_01背包问题 { 15 public int knapsack(int[] weights, int[] values, int N, int W) { //N:个数 W:容量 16 int[][] dp = new int[N + 1][W + 1]; 17 for (int i = 1; i <= N; i++) { 18 int w = weights[i - 1]; 19 int v = values[i - 1]; 20 for (int j = 1; j <= W; j++) { 21 if (j >= w) { 22 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v); 23 } else { 24 dp[i][j] = dp[i - 1][j]; 25 } 26 } 27 } 28 return dp[N][W]; 29 } 30 31 public int knapsack2(int[] weights, int[] values, int N, int W) { 32 int[] dp = new int[W + 1]; 33 for (int i = 1; i <= N; i++) { 34 int w = weights[i - 1]; 35 int v = values[i - 1]; 36 for (int j = W; j >= w; j--) { 37 dp[j] = Math.max(dp[j], dp[j - w] + v); 38 } 39 } 40 return dp[W]; 41 } 42 } 43 44 class Test_01背包问题 { 45 public static void main(String[] args) { 46 int[] weights = {5, 4, 3, 2, 1}; 47 int[] values = {1, 2, 3, 4, 5}; 48 int N = 5; 49 int W = 10; 50 demo_01背包问题 s = new demo_01背包问题(); 51 System.out.println(s.knapsack(weights, values, N, W)); 52 System.out.println(s.knapsack2(weights, values, N, W)); 53 } 54 }
Demo2、完全背包问题
1 package LeetCode.test6_dongtaiguihua; 2 3 public class demo_02完全背包问题 { 4 public int knapsack(int[] weights, int[] values, int N, int W) { 5 int[][] dp = new int[N + 1][W + 1]; 6 for (int i = 1; i <= N; i++) { 7 int w = weights[i - 1]; 8 int v = values[i - 1]; 9 for (int j = 1; j <= W; j++) { 10 if (j >= w) { 11 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w] + v); 12 // 与0-1背包问题的差别仅仅是把状态转移方程中的第二个i-1变成了i。 13 } else { 14 dp[i][j] = dp[i - 1][j]; 15 } 16 } 17 } 18 return dp[N][W]; 19 } 20 21 public int knapsack2(int[] weights, int[] values, int N, int W) { 22 // 遍历每一行的时候必须正向遍历，因为需要利用当前物品在第j-w列的信息。 23 int[] dp = new int[W + 1]; 24 for (int i = 1; i <= N; i++) { 25 int w = weights[i - 1]; 26 int v = values[i - 1]; 27 for (int j = w; j <= W; j++) { 28 dp[j] = Math.max(dp[j], dp[j - w] + v); 29 } 30 } 31 return dp[W]; 32 } 33 } 34 35 class Test_02完全背包问题 { 36 public static void main(String[] args) { 37 int[] weights = {5, 4, 3, 2, 1}; 38 int[] values = {1, 2, 3, 4, 5}; 39 int N = 5; 40 int W = 10; 41 demo_02完全背包问题 s = new demo_02完全背包问题(); 42 System.out.println(s.knapsack(weights, values, N, W)); 43 System.out.println(s.knapsack2(weights, values, N, W)); 44 } 45 }
12、分割等和子集
问题：
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 * 思路：1、不选 nums[i]，那么就从前i - 1个数中选，看是否使得这些数字的和恰好等于j，即 f[i][j] = f[i - 1][j]。 7 * 2、选择nums[i] ，在背包可以装下的情况下，那么相应的背包容量就要减去nums[i] , 8 * f[i][j]的状态就可以从f[i - 1][j - nums[i]]转移过来，即f[i][j] = f[i - 1][j - nums[i]]。 9 * 综上，两种情况只要有一个为true，f[i][j]就为true。因此状态转移方程为f[i][j] = f[i - 1][j] | f[i - 1][j - nums[i]]。 10 * 初始化：f[0][0] = true：在前0个数中，我们可以一个数都不去选，因此从前0个数中选，使得这些数字的和恰好等于0的状态为true， 11 * 其余的状态都初始化为false。 12 */ 13 public class ques_416_分割等和子集 { 14 public boolean canPartition(int[] nums) { 15 int sum = Arrays.stream(nums).reduce(0, Integer::sum); 16 if (sum % 2 != 0) { 17 return false; 18 } 19 int m = nums.length; 20 int target = sum / 2; 21 boolean[][] dp = new boolean[m + 1][target + 1]; 22 //dp[i][j]表示从前i个数中选若干个数，是否使得这些数字的和恰好等于j。 23 dp[0][0] = true; 24 for (int i = 1; i <= m; i++) { 25 for (int j = 1; j <= target; j++) { 26 if (j >= nums[i-1]) { 27 dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]; 28 }else { 29 dp[i][j] = dp[i-1][j]; 30 } 31 } 32 } 33 return dp[m][target]; 34 } 35 } 36 37 38 class Test_416 { 39 public static void main(String[] args) { 40 // int[] nums = {1, 5, 11, 5}; 41 int[] nums = {1, 5, 10, 6}; 42 ques_416_分割等和子集 s = new ques_416_分割等和子集(); 43 System.out.println(s.canPartition(nums)); 44 } 45 }
13、一和零
问题：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
1 package LeetCode.test6_dongtaiguihua; 2 3 public class ques_474_一和零 { 4 public int findMaxForm(String[] strs, int m, int n) { 5 int len = strs.length; 6 int[][][] dp = new int[len + 1][m + 1][n + 1]; 7 for (int i = 1; i <= len; i++) { 8 for (int j = 0; j <= m; j++) { 9 for (int k = 0; k <= n; k++) { 10 int countZero = countOneAndZero(strs[i - 1])[0]; 11 int countOne = countOneAndZero(strs[i - 1])[1]; 12 if (j >= countZero && k >= countOne) { 13 dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - countZero][k - countOne] + 1); 14 } else { 15 dp[i][j][k] = dp[i - 1][j][k]; 16 } 17 } 18 } 19 } 20 return dp[len][m][n]; 21 } 22 23 /** 24 * 由于dp[i][][]的每个元素值的计算只和dp[i?1][][]的元素值有关，因此可以使用滚动数组的方式， 25 * 去掉dp的第一个维度，将空间复杂度优化到 O(mn)。 26 * 实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是dp[i?1][][]中的元素值。 27 */ 28 public int findMaxForm2(String[] strs, int m, int n) { 29 int[][] dp = new int[m + 1][n + 1]; 30 for (String str : strs) { 31 int countZero = countOneAndZero(str)[0]; 32 int countOne = countOneAndZero(str)[1]; 33 for (int j = m; j >= countZero; j--) { 34 for (int k = n; k >= countOne; k--) { 35 dp[j][k] = Math.max(dp[j][k], dp[j - countZero][k - countOne] + 1); 36 } 37 } 38 } 39 return dp[m][n]; 40 } 41 42 public int[] countOneAndZero(String strs) { 43 int[] res = new int[2]; 44 for (char str : strs.toCharArray()) { 45 res[str - '0']++; 46 } 47 return res; 48 } 49 } 50 51 52 class Test_474 { 53 public static void main(String[] args) { 54 // String[] strs = {"10", "0001", "111001", "1", "0"}; 55 // int m = 5; 56 // int n = 3; 57 58 String[] strs = {"10", "0", "1"}; 59 int m = 1; 60 int n = 1; 61 ques_474_一和零 s = new ques_474_一和零(); 62 // System.out.println(s.findMaxForm(strs, m, n)); 63 System.out.println(s.findMaxForm2(strs, m, n)); 64 } 65 }
14、零钱兑换
问题：
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 * 思路：（完全背包问题） 7 * 以amount==11，coins[1,2,5]为例，总金额11可以由dp[10] + 1、dp[9] + 1、dp[6] + 1得来， 8 * 假设用1的硬币，那么就需要先凑齐10块钱，该方案下的dp[11] = dp[10] + 1； 9 * 假设用2的硬币，那么需要先凑齐9块钱，该方案下的dp[11] = dp[9] + 1； 10 * 同理，用5的硬币，dp[11] = dp[6] + 1。 11 * 所以，取他们的最小值即可，dp[i]也起到缓存的作用 12 */ 13 public class ques_322_零钱兑换 { 14 public int coinChange(int[] coins, int amount) { 15 int m = coins.length; 16 int[] dp = new int[amount + 1]; 17 Arrays.fill(dp, amount + 2); 18 dp[0] = 0; 19 for (int i = 1; i <= m; i++) { 20 for (int j = 1; j <= amount; j++) { 21 if (j >= coins[i - 1]) { 22 dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1); 23 } 24 } 25 } 26 return dp[amount] == amount + 2 ? -1 : dp[amount]; 27 } 28 } 29 30 class Test_322 { 31 public static void main(String[] args) { 32 // int[] coins = {1, 2, 5}; 33 int[] coins = {2}; 34 // int amount = 11; 35 int amount = 3; 36 ques_322_零钱兑换 s = new ques_322_零钱兑换(); 37 System.out.println(s.coinChange(coins, amount)); 38 } 39 }
六、 字符串编辑
15、编辑距离
问题：
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
1 package LeetCode.test6_dongtaiguihua; 2 3 /** 4 * 思路：dp[i][j]代表word1到i位置转换成word2到j位置需要最少步数。 5 * 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]； 6 * 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 7 * 其中，dp[i-1][j-1]表示替换操作，dp[i-1][j] 表示插入j位置/删除i位置操作，dp[i][j-1] 表示插入i位置/删除j位置操作。 8 */ 9 public class ques_72_编辑距离 { 10 public int minDistance(String word1, String word2) { 11 int m = word1.length(); 12 int n = word2.length(); 13 int[][] dp = new int[m + 1][n + 1]; 14 for (int i = 0; i <= m; i++) { 15 dp[i][0] = i; 16 } 17 for (int j = 0; j <= n; j++) { 18 dp[0][j] = j; 19 } 20 for (int i = 1; i <= m; i++) { 21 for (int j = 1; j <= n; j++) { 22 if (word1.charAt(i-1)==word2.charAt(j-1)){ 23 dp[i][j] = dp[i-1][j-1]; 24 }else { 25 dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j])) + 1; 26 } 27 } 28 } 29 return dp[m][n]; 30 } 31 } 32 33 class Test_72 { 34 public static void main(String[] args) { 35 // String word1 = "horse"; 36 // String word2 = "ros"; 37 38 String word1 = "intention"; 39 String word2 = "execution"; 40 ques_72_编辑距离 s = new ques_72_编辑距离(); 41 System.out.println(s.minDistance(word1, word2)); 42 } 43 }
16、只有两个键的键盘
问题：
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
示例 1：
输入：3
输出：3
解释：
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。
示例 2：
输入：n = 1
输出：0
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 * 思路：设dp[i]表示打印出i个A的最少操作次数。 7 * 由于只能使用「复制全部」和「粘贴」两种操作，那么要想得到i个A，必须首先拥有j个A， 8 * 使用一次「复制全部」操作，再使用若干次「粘贴」操作得到i个A。 9 * 因此，这里的j必须是i的因数，「粘贴」操作的使用次数即为i/j-1,可以枚举j进行状态转移， 10 * 这样就可以得到状态转移方程：dp[i] = min(dp[j] + i/j) 11 * 在[1, sqrt{i}]的范围内枚举j，并用j和i/j分别作为因数进行状态转移. 12 * eg: dp[6] = dp[3] + 6 / 3 (copy+paste) 13 */ 14 public class ques_650_只有两个键的键盘 { 15 public int minSteps(int n) { 16 int[] dp = new int[n + 1]; 17 Arrays.fill(dp, Integer.MAX_VALUE); 18 dp[0] = 0; 19 dp[1] = 0; 20 for (int i = 2; i <= n; i++) { 21 for (int j = 1; j * j <= i; j++) { 22 if (i % j == 0) { 23 dp[i] = Math.min(dp[i], dp[j] + i / j); //前半部分 24 dp[i] = Math.min(dp[i], dp[i / j] + j); //后半部分 25 } 26 } 27 } 28 return dp[n]; 29 } 30 } 31 32 class Test_650 { 33 public static void main(String[] args) { 34 int n = 18; 35 ques_650_只有两个键的键盘 s = new ques_650_只有两个键的键盘(); 36 System.out.println(s.minSteps(n)); 37 } 38 }
17、正则表达式匹配
问题：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
1 package LeetCode.test6_dongtaiguihua; 2 3 public class ques_10_正则表达式匹配 { 4 public boolean isMatch(String s, String p) { 5 int m = s.length(); 6 int n = p.length(); 7 boolean[][] dp = new boolean[m + 1][n + 1]; 8 dp[0][0] = true; 9 for (int i = 2; i <= n; i++) { 10 if (p.charAt(i - 1) == '*') { 11 dp[0][i] = dp[0][i - 2]; 12 } 13 } 14 // eg：s = "aab", p = "c*a*b" 15 // 假设i=2,p[1]='*',dp[0][2] = dp[0][0] = true 16 // 如果p = "dc*a*b" 则假设i=3,p[2]='*',dp[0][3] = dp[0][1] = false 17 for (int i = 1; i <= m; i++) { 18 for (int j = 1; j <= n; j++) { 19 if (p.charAt(j - 1) == '.') { 20 dp[i][j] = dp[i - 1][j - 1]; // eg：s = "ab", p = "a." 21 } else if (p.charAt(j - 1) != '*') { 22 dp[i][j] = dp[i - 1][j - 1] && (p.charAt(j - 1) == s.charAt(i - 1)); 23 // eg：s = "cab", p = "ca." 其中以a为例 24 } else if (p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.'){ 25 dp[i][j] = dp[i][j-2]; 26 // eg：s = "cdb", p = "ca." j=3 c!=d&&a!='.' 27 // dp[2][3] = dp[2][1] s = "cd", p = "ca." <-> s = "cd", p = "c" 28 } else { 29 dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i][j-2]; 30 // dp[i][j-1] 重复0次,前一个匹配 dp[i-1][j] s除去1个 dp[i][j-2] 重复0次,前一个不匹配 31 } 32 } 33 } 34 return dp[m][n]; 35 } 36 } 37 38 class Test_10 { 39 public static void main(String[] args) { 40 String s = "aa"; 41 String p = "a"; 42 ques_10_正则表达式匹配 q = new ques_10_正则表达式匹配(); 43 System.out.println(q.isMatch(s, p)); 44 } 45 }
七、 股票交易
18、买卖股票的最佳时机
问题：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
1 package LeetCode.test6_dongtaiguihua; 2 3 /** 4 * dp[i][j]表示天数[0, i]区间里，下标i这一天状态为j的时候能够获得的最大利润。其中：j=0表示当前不持股,j=1表示当前持股。 5 * dp[i][0]：规定了今天不持股，有以下两种情况：昨天不持股，今天什么都不做； 昨天持股，今天卖出股票（现金数增加）， 6 * dp[i][1]：规定了今天持股，有以下两种情况：昨天持股，今天什么都不做（现金数与昨天一样）； 7 * 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）。 8 */ 9 public class ques_121_买卖股票的最佳时机 { 10 public int maxProfit(int[] prices) { 11 int m = prices.length; 12 if (m < 2) { 13 return 0; 14 } 15 int[][] dp = new int[m + 1][2]; 16 dp[1][0] = 0; // 第一天不持股显然为0 17 dp[1][1] = -prices[0]; // 持股就需要减去第1天的股价 18 for (int i = 2; i <= m; i++) { 19 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]); 20 dp[i][1] = Math.max(dp[i - 1][1], -prices[i - 1]); 21 } 22 return dp[m][0]; 23 } 24 } 25 26 class Test_121 { 27 public static void main(String[] args) { 28 int[] prices = {7, 1, 5, 3, 6, 4}; 29 ques_121_买卖股票的最佳时机 s = new ques_121_买卖股票的最佳时机(); 30 System.out.println(s.maxProfit(prices)); 31 } 32 }
19、买卖股票的最佳时机IV
问题：
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
1 package LeetCode.test6_dongtaiguihua; 2 3 import java.util.Arrays; 4 5 /** 6 * 思路：用buy[i][j]表示对于数组prices[0..i]中的价格而言，进行恰好j笔交易，并且当前手上持有一支股票，这种情况下的最大利润； 7 * 用sell[i][j]表示恰好进行j笔交易，并且当前手上不持有股票，这种情况下的最大利润。 8 * buy[i][j]：考虑当前手上持有的股票是否是在第i天买入的。 9 * 如果是第i天买入的，那么在第i?1天时，手上不持有股票，对应状态sell[i?1][j]，并且需要扣除prices[i]的买入花费； 10 * 如果不是第i天买入的，那么在第i?1天时，手上持有股票，对应状态buy[i?1][j]。 11 * sell[i][j]：如果是第i天卖出的，那么在第i?1天时，手上持有股票，对应状态 buy[i?1][j?1]，并且需要增加prices[i]的卖出收益； 12 * 如果不是第i天卖出的，那么在第i?1天时，手上不持有股票，对应状态sell[i?1][j]。 13 */ 14 public class ques_188_买卖股票的最佳时机IV { 15 public int maxProfit(int k, int[] prices) { 16 int days = prices.length; 17 if (days < 2) { 18 return 0; 19 } 20 k = Math.min(k, days / 2); // n天最多只能进行|n/2|笔交易。 21 int[][] buy = new int[days + 1][k + 1]; 22 int[][] sell = new int[days + 1][k + 1]; 23 buy[1][0] = -prices[0]; 24 sell[1][0] = 0; 25 for (int i = 1; i <= k; ++i) { 26 buy[1][i] = sell[1][i] = Integer.MIN_VALUE / 2; 27 // 第一天不可能完成任何交易，所以buy[1][1..k]设置为一个非常小的值，表示不合法的状态; 28 // 同理将所有的sell[0][1..k]设置为一个非常小的值，表示不合法的状态. 29 } 30 for (int i = 2; i <= days; i++) { 31 buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i - 1]); 32 // 先有buy,才能有sell,二维数组初始化. 33 for (int j = 1; j <= k; j++) { 34 buy[i][j] = Math.max(sell[i - 1][j] - prices[i - 1], buy[i - 1][j]); 35 sell[i][j] = Math.max(buy[i - 1][j - 1] + prices[i - 1], sell[i - 1][j]); 36 } 37 } 38 return Arrays.stream(sell[days]).max().getAsInt(); 39 } 40 41 public int maxProfit2(int k, int[] prices) { //buy[i][j]和sell[i][j]都从buy[i?1][..]以及sell[i?1][..]转移而来. 42 int days = prices.length; 43 if (days < 2) { 44 return 0; 45 } 46 k = Math.min(k, days / 2); // n天最多只能进行|n/2|笔交易。 47 int[] buy = new int[k + 1]; 48 int[] sell = new int[k + 1]; 49 buy[0] = -prices[0]; 50 sell[0] = 0; 51 for (int i = 1; i <= k; ++i) { 52 buy[i] = sell[i] = Integer.MIN_VALUE / 2; 53 } 54 for (int i = 2; i <= days; i++) { 55 buy[0] = Math.max(buy[0], sell[0] - prices[i - 1]); 56 for (int j = 1; j <= k; j++) { 57 buy[j] = Math.max(sell[j] - prices[i - 1], buy[j]); 58 sell[j] = Math.max(buy[j - 1] + prices[i - 1], sell[j]); 59 } 60 } 61 return Arrays.stream(sell).max().getAsInt(); 62 } 63 } 64 65 66 class Test_188 { 67 public static void main(String[] args) { 68 // int k = 2; 69 // int[] prices = {2, 4, 1}; 70 int k = 2; 71 int[] prices = {3, 2, 6, 5, 0, 3}; 72 ques_188_买卖股票的最佳时机IV s = new ques_188_买卖股票的最佳时机IV(); 73 System.out.println(s.maxProfit(k, prices)); 74 System.out.println(s.maxProfit2(k, prices)); 75 } 76 }
20、最佳买卖股票时机含冷冻期
问题：
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。?
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
1 package LeetCode.test6_dongtaiguihua; 2 3 /** 4 * 思路：用 f[i]表示第i天结束之后的累计最大收益。 5 * 目前持有一支股票：f[i][0] 6 * 目前不持有任何股票，并且处于冷冻期中：f[i][1] 7 * 目前不持有任何股票，并且不处于冷冻期中：f[i][2] 8 * f[i][0]：目前持有的这一支股票可以是在第i?1天就已经持有的，对应的状态为f[i?1][0]； 9 * 或者是第i天买入的，那么第i?1天就不能持有股票并且不处于冷冻期中，对应的状态为f[i?1][2]加上买入股票的负收益prices[i]。 10 * f[i][1]：在第i天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第i?1天时必须持有一支股票， 11 * 对应的状态为f[i?1][0]加上卖出股票的正收益prices[i]。 12 * f[i][2]：在第i天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第i?1天时不持有任何股票： 13 * 如果处于冷冻期，对应的状态为f[i?1][1]；如果不处于冷冻期，对应的状态为f[i?1][2]。 14 */ 15 public class ques_309_最佳买卖股票时机含冷冻期 { 16 public int maxProfit(int[] prices) { 17 int days = prices.length; 18 int[][] dp = new int[days + 1][3]; 19 dp[1][0] = -prices[0]; 20 for (int i = 2; i <= days; i++) { 21 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i - 1]); 22 dp[i][1] = dp[i - 1][0] + prices[i - 1]; 23 dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]); 24 } 25 return Math.max(dp[days][1], dp[days][2]); 26 } 27 } 28 29 class Test_309 { 30 public static void main(String[] args) { 31 int[] prices = {1, 2, 3, 0, 2}; 32 ques_309_最佳买卖股票时机含冷冻期 s = new ques_309_最佳买卖股票时机含冷冻期(); 33 System.out.println(s.maxProfit(prices)); 34 } 35 }
八、 练习
基础难度
213. House Robber II (Medium)
强盗抢劫题目的 follow-up，如何处理环形数组呢？
53. Maximum Subarray (Easy)
经典的一维动态规划题目，试着把一维空间优化为常量吧。
343. Integer Break (Medium)
分割类型题，先尝试用动态规划求解，再思考是否有更简单的解法。
583. Delete Operation for Two Strings (Medium)
最长公共子序列的变种题。
进阶难度
646. Maximum Length of Pair Chain (Medium)
最长递增子序列的变种题，同样的，尝试用二分进行加速。
376. Wiggle Subsequence (Medium)
最长摆动子序列，通项公式比较特殊，需要仔细思考。
494. Target Sum (Medium)
如果告诉你这道题是 0-1 背包，你是否会有一些思路？
714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)
建立状态机，股票交易类问题就会迎刃而解。