二、理论基础
三、拆解问题
3.1 基础问题
3.2 背包问题
关于背包，最好的学习资料是背包九讲。但如果应对面试，掌握 01背包和完全背包就够用了。关于几种背包区别如下：
没有单纯背包的题目，都是需要通过理解题意并转换为与之对应的背包问题进行求解。
01 背包
问题描述：有 N 件物品和一个最多能装载重量为 W 的背包，第 i 件物品重量为 weight[i]，价值为 value[i]，每件商品只能选中一次。问哪些物品装入背包使得背包内物品价值总和最大 ?
二维数组模板
- 规定：以后关于 01背包问题就将横坐标
i设定为物品，纵坐标j设定为背包容量，dp[i][j]的含义就是前i件物品体积不超过j的情况下能获取的最大价值。 - 递推式：关键在于是否将物品
i放入背包：- 不放物品
i：dp[i][j] = dp[i - 1][j]。即前i个物品的最大价值等于只取前i-1个物品时的最大价值。 - 放物品
i：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]。
- 不放物品
- 初始化：
dp[i][0]这一列为 0 即可。因为背包为0无法容纳任何物品。而对于dp[0][i]表示存放编号为0的物品时获取的最大价值，换句话说，物品0能否装进背包，如果能装进，那么dp[0][i] = weight[i]，否则为 0。 - 遍历顺序（其实都可以）：
- 二维数组：先遍历物品，后遍历背包容量。
- 注意细节：当在二次
for循环中，遇到j < nums[i]的值时，需要继承dp[i - 1][j]的值。 - 遍历顺序：先物品、然后再是背包容量 ```java // 二维数组 int len = nums.length(), weight; int[][] dp = new int[len][weight + 1];
// base case：初始化第 0 行：将物品 0 和 weight 比较
// 首先遍历物品 for (int i = 0; i < len; i++) { // 接着遍历 weight for (int j = 0; j <= weight; j++) { if (j < w[i]) { // ★ 别忘记这一步，需要继承前面的值 // 当前物品过重，无法放入背包 dp[i][j] = dp[i - 1][j]; } else { // #3 这里不能写成 Math.max(a, b) + w[i]，会死人的 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + w[i]); } } }
<a name="pTm4t"></a>#### 一组数组模板一维数组是对二维数组的空间压缩，从递推公式 `dp[i][j] = Max(dp[i - 1][j], dp[i - 1][j - w]) + v` 看出，`dp[i][j]` 的值由 `dp[i - 1][j - w]` 推导出来，简单地说就是由当前位置 `(i, j)` 左上部分推导出来的。由于一维数组需要存储历史数据，那么遍历时就需要从后往前遍历才不会覆盖历史数据。<a name="uyU7P"></a>### 完全背包> 问题描述：有 N 件物品和一个最多能装载重量为 W 的背包，第 i 件物品重量为 weight[i]，价值为 value[i]，每件商品有无限个。问哪些物品装入背包使得背包内物品价值总和最大 ?完全背包和 01背包不同的地方仅限于物品数量的不同。在代码中的就是遍历顺序不一样。<a name="mcLP3"></a>#### 二维数组模板1. 递推式是 `dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i - 1]] + val[i - 1]);`。1. 我们只需要记得在第 `i` 行比较大小即可，因为第 `i` 行包含了第 `i - 1` 行的信息。1. `dp` 数组长度分别都需要 `+1`，这就可以避免对第 0 行进行初始化操作。```java// 二维数组int len = nums.length(), wei;int[][] dp = new int[len + 1][wei + 1];for (int i = 1; i <= len; i++) {for (int j = 0; j <= bag; j++) {if (weight[i - 1] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i - 1]] + val[i - 1]);}}}
一维数组模板
在 01 背包的遍历中是逆序遍历，而完全背包是正序遍历。
- 注意内循环变量
j是从weight[i - 1]开始遍历。 - 一维数组根据实际情况初始化。 ```java int[] dp = new int[wei + 1];
for (int i = 1; i <= len; i++) { // j 从 weight[i - 1] 开始遍历 for (int j = weight[i - 1]; j <= bag; j++) { dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + val[i - 1]); } }
<a name="R7mqG"></a>
### 大神总结背包问题
常见的背包问题有：
1. 组合问题：`dp[i] += dp[i - num]`
1. [377. 组合总和 Ⅳ](https://leetcode-cn.com/problems/combination-sum-iv/description/)
1. [494. 目标和](https://leetcode-cn.com/problems/target-sum/description/)
1. [518. 零钱兑换 II](https://leetcode-cn.com/problems/coin-change-2/description/)
2. True、False问题：`dp[i] = dp[i] || dp[i - num]`
1. [139. 单词拆分](https://leetcode-cn.com/problems/word-break/)
1. [416. 分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum/description/)
3. 最大最小值问题：`dp[i] = max/min(dp[i], dp[i - num] + 1) `
1. [474. 一和零](https://leetcode-cn.com/problems/ones-and-zeroes/description/)
1. [322. 零钱兑换](https://leetcode-cn.com/problems/coin-change/description/)
1. [279. 完全平方数](https://leetcode-cn.com/problems/perfect-squares/)
拿到问题，做以下分析步骤：
1. 分析是否为背包问题，如果是，属于哪一种。01 背包是物品只限使用一次，而完全背包是物品无限次数。
1. 再分析是否为组合问题。排列是需要考虑元素位置。而组合不用。
再说说遍历技巧（只针对一维数组）
1. 01 背包：先遍历物品，再遍历 `target`，内层循环为逆序。
1. 完全背包：先遍历物品，再遍历 `target`，内层循环为正序。
1. 考虑组合：先遍历 `target`，再遍历物品，内层循环为正序。
<a name="fNx56"></a>
### 题目解析
<a name="Uk7bm"></a>
#### 1. 组合问题
<a name="BrY8r"></a>
##### [377. 组合总和 Ⅳ](https://leetcode-cn.com/problems/combination-sum-iv/)
这里的细节太多了。
1. `base case` `dp[0] = 1`，这样才能正常打表。这个初始值是无意义的。
1. 由于是**排列**，需要考虑元素位置。先遍历 `target`，再遍历物品。
```java
class Solution {
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[target + 1];
// 初始化，
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i >= num) {
// 求组合，递推公式就长这样
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
494. 目标和
#1 回溯法
回溯法中使用
sum + / sum -等操作来模拟+ -。class Solution { int res; public int findTargetSumWays(int[] nums, int target) { if (nums == null) return 0; res = 0; // + - 如何表示 backTracking(nums, 0, 0, target); return res; } private void backTracking(int[] nums, int pos, int sum, int target) { if (pos == nums.length) { if (sum == target) { res ++; } return ; } backTracking(nums, pos + 1, sum + nums[pos], target); backTracking(nums, pos + 1, sum - nums[pos], target); } }#2 记忆化递归（消除重叠子问题）
对于递归函数来说，函数参数中会变的参数就是状态，而目标和中会变的就是
sum和pos。这里有一个一眼看出重叠的方法：就是令nums[pos] == 0，那么式子就变成backTracking(nums, pos + 1, sum, target); backTracking(nums, pos + 1, sum, target);这样就出现了两个状态完全相同的递归函数。只要我们找到一个，一般就能说明还存在很多重叠子问题。 ```java
class Solution { public int findTargetSumWays(int[] nums, int t) { return dfs(nums, t, 0, 0); } int dfs(int[] nums, int t, int u, int cur) { if (u == nums.length) { return cur == t ? 1 : 0; } int left = dfs(nums, t, u + 1, cur + nums[u]); int right = dfs(nums, t, u + 1, cur - nums[u]); return left + right; } }
<a name="RK850"></a>
#### 2. True、False
<a name="EJU7j"></a>
##### [416. 分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum/)
这题如果将 dp 数组定义为 `boolean[][]`，考虑的细节较多，如果面试的时候出现，考虑使用 `int[][]` 或者一组数据解决。
<a name="rGuUI"></a>
##### 二维 `boolean[][]` 数组
1. `boolean[i][j]` 数组表示前 `i` 个数能否恰好构成 `j`。
1. `#1` 需要初始化为 `true`。然后对第 `0` 行进行初始化：遇到等于 `target` 时为 `true`。
1. `#2` 需要继承 `dp[i - 1][j]` 的值
```java
class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) return true;
int len = nums.length, target = 0;
for (int num : nums) { target += num; }
if ((target & 1) == 1) return false;
target /= 2;
boolean[][] dp = new boolean[len][target + 1];
// base case：初始化第一行
// #1
dp[0][0] = true;
if (nums[0] == target) { dp[0][nums[0]] = true; }
// caculate dp table
for (int i = 1; i < len; i++) {
for (int j = 0; j <= target; j++) {
if (j < nums[i]) {
// #2
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[len - 1][target];
}
}
一维 boolean[] 数组
注意
#2内部写法class Solution { public boolean canPartition(int[] nums) { if (nums == null || nums.length == 0) return true; int len = nums.length, target = 0; for (int num : nums) { target += num; } if ((target & 1) == 1) return false; target /= 2; boolean[] dp = new boolean[target + 1]; // base case：初始化第一行 dp[0] = true; if (nums[0] == target) { dp[nums[0]] = true; } // caculate dp table for (int i = 1; i < len; i++) { for (int j = target; j >= 0; j--) { if (j >= nums[i]) { dp[j] = dp[j] || dp[j - nums[i]]; } } } // 还可以写成这种形式，效率会高一点 for (int i = 1; i < len; i++) { // #2 注意这里的写法 for (int j = target; j >= nums[i]; j--) { dp[j] = dp[j] || dp[j - nums[i]]; } } return dp[target]; } }3. 最大值最小值问题
322. 零钱兑换
- 数组含义：
dp[i][j]表示前i个硬币可以凑成j所需最小硬币数量。 - 将
dp[]一维数组初始化为amount可以避免整数类型溢出问题。 -
279. 完全平方数
转化为完全背包问题： 物品：完全平方数，比如
、
等等。- target：就是
n。 -
HJ16 购物单
这是一道基于 01背包问题的改编题，十分有意思。
属于 01背包框架，但加上了一些额外的条件：主件和附件归属问题，如果选取附件，则必拿对应的主件。这里的思路是，我们只将主件考虑为物品，而附件只是附属品。因为最多只能有 2 个附件，因此我们可以通过枚举所有可能的情况并取最大值。3.3 打家劫舍
★198. 打家劫舍
主要是讨论第
i取还是不取，得出dp[i] =class Solution { public int rob(int[] nums) { // dp[i] = Max(dp[i - 1], dp[i - 2] + nusm[i]); if (nums == null || nums.length == 0) return 0; int n = nums.length; int[] dp = new int[n + 1]; // base case dp[1] = nums[0]; for (int i = 2; i <= n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]); } return dp[n]; } }★213. 打家劫舍 II
class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; if (n == 1) return nums[0]; int[] includeFirseHouse = new int[n - 1]; int[] includeLastHouse = new int[n - 1]; System.arraycopy(nums, 0, includeFirseHouse, 0, n - 1); System.arraycopy(nums, 1, includeLastHouse, 0, n - 1); return Math.max(robHouse(includeFirseHouse), robHouse(includeLastHouse)); } private int robHouse(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; dp[1] = nums[0]; for (int i = 2; i <= n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]); } return dp[n]; } }256. 粉刷房子
房子不能刷成相同的颜色，所以我们要打表的过程中需要针对不同的颜色进行区分比较。 ```java class Solution { public int minCost(int[][] costs) {
// 可被粉刷成三种中的一种， if (costs == null) return 0; // costs[0][0]：红色，1：绿色，2：蓝色 // 求刷完房子最小花费成本 int n = costs.length; // 房间数 // dp[i][0] 表示房间 i 粉刷成红色所花费的最小的总成本 // n 还是 n+1 int[][] dp = new int[n][3]; dp[0][0] = costs[0][0]; dp[0][1] = costs[0][1]; dp[0][2] = costs[0][2];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
}
return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
}
}
<a name="KqSf4"></a>
## 3.4 股票问题
<a name="izlN3"></a>
## 3.5 子序列问题
354. 俄罗斯套娃信封问题 LeetCode 题解链接 困难 🤩🤩🤩🤩🤩
354. 最大整除子集 LeetCode 题解链接 中等 🤩🤩🤩🤩
354. 等差数列划分 II - 子序列 LeetCode 题解链接 困难 🤩🤩🤩🤩🤩
354. 删除并获得点数 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
354. 最长湍流子数组 LeetCode 题解链接 中等 🤩🤩🤩
354. 不相交的线 LeetCode 题解链接 中等 🤩🤩🤩🤩
354. 最长公共子序列 LeetCode 题解链接 中等 🤩🤩🤩🤩
354. 粉刷房子 III LeetCode 题解链接 困难 🤩🤩🤩🤩
354. 得到子序列的最少操作次数 LeetCode 题解链接 困难 🤩🤩🤩🤩🤩
<a name="WyL5W"></a>
### ★ [300. 最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
<br />本题求子序列的**长度**，我们需要在第二层 `for` 循环在 `[0, i)` 区间通过枚举得到最长长度。<br />时间复杂度 。
```java
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
// dp[i] 表示必须包含位置 i 所能构成的最大子序列长度
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
if (dp[i] > res) res = dp[i];
}
return res;
}
}
还有一种二分查找解法（切牌法），思路如下：
- 遍历
[0, nums.length)，每一个元素k和当前牌的顶部比较。如果k大于任意牌堆顶，则创建一个新的堆。 确定元素
k位于哪个堆顶的过程就是通过二分查找来解决，使用的是寻找左边界模板。class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) return 0; int[] top = new int[nums.length]; // 当前有多少堆 int piles = 0; // 遍历元素 nums for (int i = 0; i < nums.length; i++) { // 左边界二分查找， int left = 0, right = piles; int target = nums[i]; while (left < right) { int mid = left + (right - left) / 2; if (top[mid] == target) { right = mid; } else if (top[mid] > target) { right = mid; } else { left = mid + 1; } } // 当前元素 i 比堆顶都大，另建一个堆 if (left == piles) piles++; // 更新堆顶元素 top[left] = target; } return piles; } }写法二：
class Solution { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; // 创建「n+1」长度的堆 int[] heap = new int[n + 1]; // base case：首堆为 nums[0] heap[1] = nums[0]; int piles = 1; for (int i : nums) { // 如果大于piles指向的元素，则新建一个堆 if (i > heap[piles]) { heap[ ++piles ] = i; } else { // 否则，使用二分查找搜索左边界，注意，这里 left 指向 1，否则会出错 int left = 1, right = piles; while (left < right) { int mid = left + (right - left) / 2; if (i == heap[mid]) { // 相等，收缩右边界 right = mid; } else if (i > heap[mid]) { left = mid + 1; } else { right = mid; } } // 找到合适的堆，更新堆的值 heap[left] = i; } } return piles; } }变种：NC91 最长递增子序列
解题细节：使用两个
dp数组。dp[]存储以arr[i]结尾的最长长度。end[i]存储长度为i时末尾最小的数。public int[] LIS (int[] arr) { if (arr.length == 0) return new int[0]; int len = arr.length; // dp[i]：以 arr[i] 结尾时最长长度 int[] dp = new int[len]; // end[i]：长度为 i 时末尾最小数值 int[] end = new int[len + 1]; // 初始化 dp[0] = 1; end[1] = arr[0]; int maxLength = 1; for (int i = 0; i < arr.length; i++) { int target = arr[i]; if (target > end[maxLength]) { // 新建一个堆，更新 end[]数组，表示长度为 maxLen 的末尾最小数为 target end[ ++maxLength ] = target; dp[i] = maxLength; } else { // 使用左边界二分查找模板 int left = 1, right = maxLength; while (left < right) { int mid = left + (right - left) / 2; if (end[mid] == target) { right = mid; } else if (end[mid] > target) { right = mid; } else { left = mid + 1; } } // 找到合适的 left，更新 end[left] = target; // 对于 end 的 left 来说，这个就是 i 对应的长度呀 dp[i] = left; } } // 构造结果，从后往前遍历，数组长度为 maxLength int[] result = new int[maxLength]; for (int i = arr.length - 1; i >= 0; i--) { // 判断 dp[i] 是否为最长长度的一部分 if (dp[i] == maxLength) { result[--maxLength] = arr[i]; } } return result; }674. 最长连续递增序列（求子序列长度）
使用贪心算法。class Solution { public int findLengthOfLCIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int res = 1; int count = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1]) { count++; } else { count = 1; } res = Math.max(count, res); } return res; } }动态规划求解明确
dp[i]数组定义：dp[i]表示以i结尾的最长连续递增序列的长度。class Solution { public int findLengthOfLCIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int len = nums.length; // dp[i] 表示以 i 结尾的最长递增子序列 int[] dp = new int[len]; dp[0] = 1; int maxVal = 1; for (int i = 1; i < len; i++) { if (nums[i] > nums[i - 1]) { dp[i] = dp[i - 1] + 1; } else { dp[i] = 1; } maxVal = Math.max(maxVal, dp[i]); } return maxVal; } }673. 最长递增子序列的个数（求子序列个数）
与求子序列长度不同，这里是求序列个数。因此，我们只需要在子序列长度的基础上增加额外的辅助信息即可。我们需要额外定义一个 dp 数组，叫做
g[i]，表示以nums[i]结尾的最长上升子序列的个数（最长、个数）。那么对于g[i]的状态转换解析如下：每个元素能单独成序，因此初始值
g[i] = 1。- 枚举
[0, i]之间的元素，判断是否能组成最长子序列，并记录最长长度出现的次数即可。
解析需注意以下细节：
- 定义两个数组，数组
g[i]表示以nums[i]结尾的最长递增子序列的个数。 - 更新
dp[i]和g[i]的时机。在进行枚举过程中，当nums[i] > nums[j]时，则需要根据长度分别更新dp[i]和g[i]。 - 注意，
g[i]的值是需要加上g[j]的值。 - 在计算最长子序列个数的个数时，需要得到最长长度
maxLen，然后遍历dp[i]，累加g[i]就能得到最终值。 第二层循环变量
j的范围是[0, i)。class Solution { public int findNumberOfLIS(int[] nums) { // 求最长递增子序列的个数 if (nums == null || nums.length == 0) return 0; int len = nums.length; // dp[i] 表示以 i 结尾的最长递增子序列长度 int[] dp = new int[len]; Arrays.fill(dp, 1); // g[i] 表示以 i 结尾的最长长度个数 int[] g = new int[len]; Arrays.fill(g, 1); // 最长递增序列长度 int maxLen = 1; for (int i = 0; i < len; i++) { // j 不能越过 i for (int j = 0; j < i; j++) { // 构成递增序列 if (nums[i] > nums[j]) { // 当前长度 int curLen = dp[j] + 1; if (curLen > dp[i]) { // 最大长度，两个dp数组都需要更新 dp[i] = curLen; g[i] = g[j]; } else if (curLen == dp[i]) { g[i] += g[j]; } } maxLen = Math.max(maxLen, dp[i]); } } int res = 0; for (int i = 0; i < len; i++) { // 收集所有长度为maxLen对应的次数 if (dp[i] == maxLen) res += g[i]; } return res; } }★1143. 最长公共子序列
注意以下区别：
子序列和子串的区别。子序列是相对位置不可变，中间可以任意删除字符。而子串不允许删除字符。求子序列一般使用动态规划，而求子串一般使用滑动窗口。详见 3. 无重复字符的最长子串
class Solution { public int longestCommonSubsequence(String text1, String text2) { if (text1 == null || text2 == null) return 0; // dp[i][j] 表示 (0, i) 和 (0, j) 两个字符串所拥有的LCS int len1 = text1.length(), len2 = text2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; 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 - 1][j], dp[i][j - 1]); } } } return dp[len1][len2]; } }NC127 最长公共子串
本题带给我的提升是保留其它信息，因为使用动态规划，一般结果都在数组里面，但是在某些题中dp[]数组只是辅助信息。比如在本题中，dp[][]数组只记录以i,j结尾的最长公共子串长度，而题目要求返回子串。所以我们需要两个变量endIndex和maxLen分别表示maxLen长度的末尾索引位置。这样我们就可以截取子串并返回。
本题的状态转移方程也比较简单，就是比较末尾字符串是否相同，如果相同则在dp[i - 1][j - 1]的基础上+1，否则不修改任何值，即0。public class Solution { /** * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ public String LCS (String s1, String s2) { if (s1 == null || s2 == null) return ""; int n1 = s1.length(); int n2 = s2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; int maxLen = 0, endIndex = 0; for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } if (dp[i][j] > maxLen) { maxLen = dp[i][j]; endIndex = i; } } } return s1.substring(endIndex - maxLen, endIndex); } }★72. 编辑距离
```java class Solution { public int minDistance(String word1, String word2) {
// 定义dp数组及下标含义 // i、j为字符串的长度， // dp[i][j]表示[0, i-1], [0, j-1]两个字符串转换成一样的需要的最少操作数 // 可以通过插入一个字符、删除一个字符、替换一个字符 // 1.当字符串相等，则不需要进行任何操作，有dp[i][j] = dp[i-1][j-1] // 2.当字符串不相等，则需要进行调整 // 2.1 替换：把字符串 word1[i]替换成word[j]相等，则有 dp[i][j] = dp[i-1][j-1]+1 // 2.2 插入：在word1末尾插入一个与word2[j]相等的字符，则有dp[i][j] = dp[i][j-1] + 1 // 2.3 删除：将字符word1[i]删除，则有dp[i][j] = dp[i-1][j] + 1
// 初始化：第一行和第一列。当有一个字符串长度为0时，转化为另外一个字符串只有能进行插入或删除操作
if (word1 == null && word2 == null) return 0;
if (word1 == null || word2 == null) return word1 == null ? word2.length() : word1.length();
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 初始化
for (int i = 0; i <= n; i++) { dp[0][i] = i; }
for (int i = 0; i <= m; i++) { dp[i][0] = i; }
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
}
}
}
return dp[m][n];
}
}
<a name="LLQrE"></a>
### [44. 通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/)
1. base case 是对模式串那一行进行初始化。
1. 理解 `dp[i][j] = dp[i - 1][j] || dp[i][j - 1];` 这一行。`dp[i][j - 1]` 表示代表的是空字符，例如 `ab, ab`。`dp[i - 1][j]` 表示代表的是非空字符，例如 `abcd, ab`。
```java
class Solution {
public boolean isMatch(String s, String p) {
if ((s == null && p == null) || p == null) return false;
int n = s.length(), m = p.length();
// 橫坐标是模式串，纵坐标是字符串
boolean[][] dp = new boolean[m + 1][n + 1];
// base case
dp[0][0] = true;
for (int i = 1; i <= m && p.charAt(i - 1) == '*'; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(i - 1) == '?' || s.charAt(j - 1) == p.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(i - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[m][n];
}
}
926. 将字符串翻转到单调递增
思路一：使用 300. 最长递增子序列 算法，找到最长子序列，剩下的就是需要翻转次数。可以使用二分算法：
class Solution {
public int minFlipsMonoIncr(String s) {
// LIS
int[] d = new int[s.length()];
Arrays.fill(d, -1);
int len = 0;// 队伍的长度
int i = 0;// 0放入队伍中的位置
for(char c : s.toCharArray()) {
if(c == '0') {
d[i] = 0;
if(i == len) len++;// 此时队伍中没有1
i++;
} else {
d[len] = 1;// 1放入队伍的末尾
len++;
}
}
return s.length() - len;
}
}
可以看出，维护的 d[] 本身实际上并未使用，上面的代码只是为了便于理解的中间过程，最终可以简化为
class Solution {
public int minFlipsMonoIncr(String s) {
// LIS
int len = 0;// 队伍的长度
int i = 0;// 0放入队伍中的位置
for(char c : s.toCharArray()) {
if(c == '0') {
if(i == len) len++;// 此时队伍中没有1
i++;
} else {
len++;
}
}
return s.length() - len;
}
}
思路二：动态规划。dp[i][0] 表示以 0 结尾的最小翻转次数，dp[i][1] 表示以 1 结尾的最小翻转次数。状态转移过程是判断末尾字符是否为 0：
s[i] == '0'，dp[i][0] = dp[i - 1][0]，dp[1][1] = Min(dp[i - 1][0], dp[i - 1][1]) + 1s[i] == '1'，dp[i][0] = dp[i - 1][0] + 1，dp[1][1] = Min(dp[i - 1][0], dp[i - 1][1]) + 1class Solution { public int minFlipsMonoIncr(String s) { if (s == null || s.length() == 0) return 0; // ① 字符可任意翻转，求最小翻转次数 int n = s.length(); int[][] dp = new int[n][2]; dp[0][0] = s.charAt(0) == '0' ? 0 : 1; dp[0][1] = s.charAt(0) == '1' ? 0 : 1; for (int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][0] + (s.charAt(i) == '0' ? 0 : 1); dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + (s.charAt(i) == '0' ? 1 : 0); } return Math.min(dp[n - 1][0], dp[n - 1][1]); } }
四、总结
[
若有收获，就点个赞吧
0 人点赞
