前言
动态规划的核心设计思想是数学归纳法
假如我们想证明一个数学结论：
- 那么先假设这个结论在
k < n时成立- 想办法推导证明出
k = n的时候此结论也成立。
是需要一个 dp 数组嘛？
- 可以假设
dp[0...i - 1]都已经被算出来了 - 然后问自己：怎么通过这些结果算出
dp[i]？ - 首先要定义清楚的
dp数组的含义，即dp[i]的值到底代表是什么？
Tips：”子序列“ 和 ”子串“ 区别
- 子串一定是连续的
- 子序列不一定是连续的
子序列问题是最常见的算法问题，而且并不好解决。
一旦涉及子序列和最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n ^ 2)
既然用到动态规划，那就要定义
dp数组，寻找状态转移关系。
两种思路：
- 第一种思路模板是一个一维的
dp数组：
int n = array.length;
int [] dp = new int[n];
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
dp[i] = 最值(dp[i], dp[j] + ...)
}
}
- 第二种思路模板是一个二维的
dp数组：
int n = arr.length;
int [][] dp = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (arr[i] == arr[j])
dp[i][j] = dp[i][j] + ...
else
dp[i][j] = 最值(...)
}
}
题目
（1）LeetCode 300 最长递增子序列
题目描述
给你一个整数数组 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
思路解法
定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
可以推出 base case：dp[i] 初始值为 1, 因为以 nums[i] 结尾的最长递增子序列起码要包含它自己。
public class LeetCode_300 {
// 方法一：
// Time: o(n^2), Space: o(n), Faster: 27.93%
public int lengthOfLISDP(int [] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length, max = 1;
int [] d = new int[n];
d[0] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int cur = nums[i] > nums[j] ? d[j] + 1 : 1;
d[i] = Math.max(d[i], cur);
}
max = Math.max(max, d[i]);
}
return max;
}
// 方法二：
// Time: o(n * log(n)), Space: o(n), Faster: 92.62%
public int lengthOfLISBinarySearch(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// 牌堆数初始化为 0
int len = 0;
int [] top = new int[nums.length];
for (int x : nums) {
int left = binarySearchInsertPosition(top, len, x);
// 把这张牌放到牌堆顶，牌堆顶的牌是这个堆最小的
top[left] = x;
// 没找到合适的牌堆，新建一堆
if (left == len) ++len;
}
return len;
}
private int binarySearchInsertPosition(int[] d, int len, int x) {
int low = 0, high = len - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (x < d[mid]) high = mid - 1;
else if (x > d[mid]) low = mid + 1;
else return mid;
}
return low;
}
}
（2）LeetCode 53 最大子序和
题目描述
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路解法
题目解读：以 nums[i] 为结尾的 “最大子数组和” 为 dp[i]
使用数学归纳法来找状态转移关系：假设已经算出了 dp[i - 1], 如何推导出 dp[i] 呢？
dp[i] 有两种 “选择”：
- 要么与前面的相邻子数组连接，形成一个和更大的子树组
- 要么不与前面的子数组连接，自成一派，自己作为一个子数组。
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], num[i] + dp[i - 1]);
思路：
- 方法一：暴力求法，两层
for循环 - 方法二：
dp方法。 - 方法三：遍历一遍，负数 + 负数没有任何意义 前面累加值为负数，则对后面没有正向的贡献， 所以可以直接舍弃前面这段子序列的和
这里主要讲的是方法三：
public class LeetCode_53 {
// Time: O(n), Space: O(1), Faster: 95.05%
public int maxSumOfSubArray(int[] nums) {
int max = Integer.MIN_VALUE, cur = 0;
for (int i = 0; i < nums.length; ++i) {
// 前面累加值为负数，对后面没有正向的贡献，可以直接舍弃前面的子序列的和
cur = cur <= 0 ? nums[i] : (cur + nums[i]);
max = Math.max(max, cur);
}
return max;
}
}
总结：
-
dp大部分还是有规律可循的。 -
dp数组的定义是 “以nums[i]为结尾的最大子数组和 / 最长递增子序列为dp[i]”。 -
因为只有这样的定义才能使
dp[i + 1]和dp[i]建立联系，利用数学归纳发写出状态转移方程。
（3）LeetCode 152 连续子序列的最大乘积
题目描述
这个题目说的是，给你一个整数数组，你要找到乘积最大的连续子序列，然后返回它的乘积。
比如说，给你的数组是：
8, 1, -2, 4, -1
这个数组中连续子序列的最大乘积是 64，连续子序列就是数组本身。
思路解法
解法有两种：
- 暴力法：两层
for循环 - 动态规划：在遍历数组时候，要保留当前最大乘积、当前最小乘积
- 当前最大乘积
- 当前最小乘积
图解如下：
AC 代码：
public class LeetCode_152 {
// 方式一：暴力法
// Time: O(n ^ 2), Space: O(1), Faster: 5.01%
public int maxProduct2(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; ++i) {
int sum = nums[i];
max = Math.max(max, sum);
for (int j = i + 1; j < nums.length; ++j) {
sum *= nums[j];
max = Math.max(sum, max);
}
}
return max;
}
// 方式二：动态规划
// Time: o(n), Space: o(1), Faster: 66.15%
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int max = nums[0], currMax = nums[0], currMin = nums[0];
for (int i = 1; i < nums.length; ++i) {
int a = currMax * nums[i], b = currMin * nums[i], c = nums[i];
currMax = max(a, b, c);
currMin = min(a, b, c);
max = Math.max(max, currMax);
}
return max;
}
private int max(int a, int b, int c) {
return Math.max(Math.max(a, b), c);
}
private int min(int a, int b, int c) {
return Math.min(Math.min(a, b), c);
}
}
（4）LeetCode 354 俄罗斯套娃信封问题
题目描述
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明: 不允许旋转信封。
示例:
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
信封嵌套问题实际上是最长递增子序列问题上升到二维，其解法就需要先按照特定的规则排序，之后转换为一个一维的最长递增子序列问题，最后用二分搜索框架中的技巧来解决。
这道题目其实是 最长递增子序列（LOngest Incresing Subsequence, LIS） 的一个变种。
每次合法的嵌套是大的套小的，相当于找一个最长递增的子序列，其长度就是最多能嵌套的信封个数。
一个直接的想法就是，通过 w * h 计算面积，然后对面积进行标准的 LIS 算法。但是稍加思考就会发现这样不行，比如 1 * 10 大于 3 * 3, 但是显然这样的两个信封是无法互相嵌套的。
思路解法
思路步骤：
- 先对宽度
w进行升序排序，如果遇到w相同的情况，则按照高度h降序排序。 - 之后把所有的
h作为一个数组，在这个数组上计算出的LIS的长度就是答案。
步骤1，如图：
步骤2，如图：
public class LeetCode_354 {
// Time: O(n * log(n)), Space: O(n), Faster: 87.03%
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按照宽度升序排列，如果宽度一样，则按高度降序排列
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
// 对高度数组寻找 LIS
int [] height = new int[n];
for (int i = 0; i < n; ++i) {
height[i] = envelopes[i][1];
}
return lengthOfLISBinarySearch(height);
}
// Time: o(n * log(n)), Space: o(n), Faster: 92.62%
private int lengthOfLISBinarySearch(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// 牌堆数初始化为 0
int len = 0;
int [] top = new int[nums.length];
for (int x : nums) {
int left = binarySearchInsertPosition(top, len, x);
// 把这张牌放到牌堆顶
top[left] = x;
// 没找到合适的牌堆，新建一堆
if (left == len) ++len;
}
return len;
}
private int binarySearchInsertPosition(int[] d, int len, int x) {
int low = 0, high = len - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (x < d[mid]) high = mid - 1;
else if (x > d[mid]) low = mid + 1;
else return mid;
}
return low;
}
}
总结：
其实这种问题还可以扩展到三维，比如过说嵌套箱子，每个箱子有长、宽、高三个维度，请你计算最多能嵌套几个箱子？
按之前思路，可能会想：先把前两个维度（长和宽）按信封嵌套的思路求一个嵌套序列，最后在这个序列的第三个维度（高度）找一下 LIS，就能算出答案。
实际上，这个思路是错误的。这类问题叫做 “偏序问题”，上升到三维会使难度巨幅提升，需要借助一种高级数据结构 “树状数组”。
（5）LeetCode 1312 让字符串成为回文串的最少插入次数
题目描述
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
示例 4：
输入：s = "g"
输出：0
示例 5：
输入：s = "no"
输出：1
提示：
1 <=
s.length<= 500s中所有字符都是小写字母。
题干分析
要找最少的插入次数，那肯定要穷举喽。
每次都可以在两个字符的中间插入任意一个字符，外加判断字符串是否为回文字符串，它的时间复杂度肯定暴增，而且是指数级的。
动态规划标准套路：
- 第一步要明确：状态 和 选择
- 第二步要明确：
dp数组的定义 - 第三步：根据 “选择”，思考状态转移的逻辑
1. 第一步要明确：状态 和 选择
- 状态：“指针
i” 和 “指针j”- 选择：“插入” 或者 “不插入”
2. 第二步要明确：dp 数组的定义
dp数组的定义：dp[i][j], 对字符串s[i..j]，最少需要进行dp[i][j]次插入才能变成回文串。
- 最终答案：
dp[0][n - 1]的大小（n为s的长度）
base case： 当i == j时，dp[i][j] = 0, 因为当i == j时s[i..j]就是一个字符，本身就是回文串，所以不需要进行任何插入操作;
3. 第三步：根据 “选择”，思考状态转移的逻辑
- 如果 s[i] == s[j]，不需要进行任何插入，只要知道如何把
s[i+1..j-1]变成回文串即可
- 如果 s[i] != s[j]，分情况讨论，看下文。
分析第三步：状态转移方程
想要计算 dp[i][j] 的值，能从子问题 dp[i + 1][j - 1] 推出 dp[i][j] 值嘛？
也就认为
s[i+1 .. j-1]已经是一个回文串了，所以通过dp[i+1][j-1]推导dp[i][j]的关键在于s[i]和s[j]。
-
如果 s[i] == s[j]，不需要进行任何插入，只要知道如何把
s[i+1..j-1]变成回文串即可。
如图：
// 翻译成代码
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
}
- 如果 s[i] != s[j]，分情况讨论：
当 s[i] != s[j] 时，插入两次肯定可以让 s[i..j] 变成回文串，但是不一定是插入次数最少的。
如图：
第一步：将
s[i]插到s[j]的左边第二步：将
s[j]插到s[i]的左边
特殊情况：
只需要插入一个字符即可使得
s[i..j]变成回文，如下图：
这种情况，
s[i+1..j]或s[i..j - 1]原本就是回文串，那么就不需要插入，只需要插入另一个即可。
if (s[i] != s[j]) {
// 步骤一选择代价较小的
// 步骤二必然要进行一次插入
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
思路解法
状态转移方程中 dp[i][j] 和 dp[i + 1][j] 、dp[i][j - 1]、dp[i + 1][j - 1] 三个状态有关，为了保证每次计算 dp[i][j] 时，这三个状态都已经被计算，一般选择从下向上，从左到右遍历 dp 数组：
public class LeetCode_1312 {
// Time: O(n ^ 2), Space: O(n ^ 2), Faster: 60.65%
public int minInsertions(String s) {
int n = s.length();
// 定义： 对 s[i..j], 最少需要插入 dp[i][j] 次才能变成回文串
// base case： dp 数组全部初始化为 0
int [][] dp = new int[n][n];
// 从下向上遍历
for (int i = n - 2; i >= 0; --i) {
// 从左向右遍历
for (int j = i + 1; j < n; ++j) {
// 根据 s[i] 和 s[j] 进行状态转移
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j -1];
} else {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
// 根据 dp 数组的定义，题目要求的答案是 dp[0][n - 1]
return dp[0][n - 1];
}
}
优化：
dp数组的状态只和和它相邻的状态有关，所以dp数组是可以压缩成一维的。
public class LeetCode_1312 {
// Time: O(n ^ 2), Space: O(n), Faster: 77.81%
public int minInsertions(String s) {
int n = s.length();
int [] dp = new int[n];
int temp = 0;
for (int i = n - 2; i >= 0; --i) {
// 记录 dp[i+1][j-1]
int pre = 0;
for (int j = i + 1; j < n; ++j) {
temp = dp[j];
if (s.charAt(i) == s.charAt(j)) {
// dp[i][j] = dp[i+1][j-1];
dp[j] = pre;
} else {
// dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
dp[j] = Math.min(dp[j], dp[j - 1]) + 1;
}
pre = temp;
}
}
return dp[n - 1];
}
}
（6）LeetCode 1143 最长公共子序列
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
题干分析
最长公共子序列（Longest Common Subsequence, LCS）是一道非常经典的面试题目，因为它的解法是典型的二维动态规划。
这个算法稍微加改造就可以用于解决其他问题，所以说
LCS算法是值得掌握的。
动态规划思路：
- 第一步：一定要明确
dp数组的含义 - 定义
base case - 找状态转移方程
1. 第一步：一定要明确 dp 数组的含义。
对于两个字符串的动态规划问题，套路是通用的，一般都需要一个二维 dp 数组。
比如对于字符串 s1 和 s2，一般来说要构造一个这样的 DP table：
dp[i][j] 含义是：对于 s1[0..i - 1] 和 s2[0..j - 1]，它们的 LCS 长度是 dp[i][j]。
比如上图这个例子，dp[2][4] = 2 含义就是：对于 "ac" 和 "babc"，它们的 LCS 长度是2。根据这个定义，最终想得到的答案应该是 dp[3][6]。
2. 定义 base case
专门让索引为 0 的行和列表示空串，dp[0][..] 和 dp[..][0] 都应该初始化为 0，这就是 base case。
比如按照刚才 dp 数组的定义，dp[0][3] = 0 的含义是：对于空字符串 "" 和 "bab"，其 LCS 的长度为 0。
因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0
3. 找状态转移方程
做 “选择”。
求 s1 和 s2 的最长公共子序列，设：子序列为 lcs。
那么对于 s1 和 s2 中的每个字符，有什么选择？
很简单，两种选择，要么在
lcs中，要么不在。
如图：
对于 s1[i] 和 s2[j]，怎么知道它们到底在不在 lcs 中？
可以很容易想到的是，如果某个字符在 lcs 中，那么这个字符肯定同时存在与 s1 和 s2 中，因为 lcs 是最长公共子序列。
dp(i, j) 表示 s1[0...i] 和 s2[0...j] 中最长公共子序列的长度，这样就可以找到状态转移关系：
- 如果
s1[i] == s2[j]
说明这个公共字符一定在
lcs中，如果知道了s1[0..i-1]和s2[0..j-1]中的lcs长度，再加 1 就是s1[0..i]和s2[0..j]中lcs的长度。 根据dp函数的定义，如下：if (str1[i] == str2[j]) dp[i][j] = dp(i - 1, j - 1) + 1; 复制代码
- 如果
s1[i] != s2[j]
说明
s1[i]和s2[j]这两个字符至少有一个不在lcs中，那到底是哪个字符不在lcs中呢？ 根据dp函数的定义，如下：if (str1[i] != str2[j]) dp[i][j] = Math.max(dp(i - 1, j), dp(i, j - 1));
明白了状态转移方程，可以直接写出解法。
思路解法
思路：
- 二维数组
dp -
dp压缩
public class LeetCode_1143 {
// Time: O(n ^ 2), Space: O(m * n), Faster: 72.28%
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
// 定义： 对于 s1[0..i-1] 和 s2[0..j-1], 它们的 lcs 长度是 dp[i][j]
// base case: dp[0][..] = dp[..][0] = 0 已初始化
int [][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
// 状态转移逻辑
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
}
网友评论