动态规划和递归真的有点难搞
回溯应该是一种典型的递归，回溯的递归和我写的动态规划一中的第二题是类似的，它是不能对i、j进行变动然后进行递归的，例如Math.min(dp(i+1,j),dp(i,j+1))，它取下次递归传递的参数只能借助一下for循环采取记录值的方式，类似与回溯的递归方式、、
72、编辑距离
labuladong讲解
看他这个讲解就好了，写的够全够好的了
设两个字符串分别为 "rad" 和 "apple"，为了把 s1 变成 s2
他这个题目是从后往前变，那我们自己看的时候不要只看别人的代码思路，我们可以从前往后写，但凡没有自己动脑，动手写的就不是自己的，为什么多线程现在写的还是稀碎，就是因为动手太少了
还有就是质变和量变的问题，量变不一定是非要是做过那一道题然后反复看，每天反复看到把这个题目都背下来了，就很难去理解了，每天都去刷错题，未必是最高效的学习方法，我觉得应该是一段时间都刷一种类型题，没有完全理解的时候就一直刷，直到有自己的理解时再回头看，这样更容易去理解，更容易去总结规律，而不是背诵，把工科学成文科也是种悲哀、、
首先看完题解思路，这个大致的框架自己没有写出来也是超乎自己的预料的，因为这种代码刚在公司写过
if s1[i] == s2[j]:
啥都别做（skip）
i, j 同时向前移动
else:
三选一：
插入（insert）
删除（delete）
替换（replace）
其次，就是这个代码
递归代码无动态规划记录：
首先是这个往下递归的写法,i、j改变基础上再加一个min
找到插入、删除、替换三种方法中的最小值
递归的意义也在此，与遍历树的思路一致
return min(
dp(s1, i, s2, j - 1) + 1, // 插入
dp(s1, i - 1, s2, j) + 1, // 删除
dp(s1, i - 1, s2, j - 1) + 1 // 替换
);
其次就是停止条件，为什么一个为-1，返回另一个的+1
首先它是索引值，所以是+1
如果一个到头了，没有数值了，另一个剩余的字母都要进行删除，删除所产生的操作次数为 另一个的索引值+1
if (i == -1) return j + 1;
if (j == -1) return i + 1;
int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
// i，j 初始化指向最后一个索引
return dp(s1, m - 1, s2, n - 1);
}
// 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
int dp(String s1, int i, String s2, int j) {
// base case
if (i == -1) return j + 1;
if (j == -1) return i + 1;
if (s1.charAt(i) == s2.charAt(j)) {
return dp(s1, i - 1, s2, j - 1); // 啥都不做
}
return min(
dp(s1, i, s2, j - 1) + 1, // 插入
dp(s1, i - 1, s2, j) + 1, // 删除
dp(s1, i - 1, s2, j - 1) + 1 // 替换
);
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
它的动态规划代码：
class Solution {
// 备忘录
int[][] memo;
public int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 备忘录初始化为特殊值，代表还未计算
memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dp(s1, m - 1, s2, n - 1);
}
int dp(String s1, int i, String s2, int j) {
if (i == -1) return j + 1;
if (j == -1) return i + 1;
// 查备忘录，避免重叠子问题
if (memo[i][j] != -1) {
return memo[i][j];
}
// 状态转移，结果存入备忘录
if (s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = dp(s1, i - 1, s2, j - 1);
} else {
memo[i][j] = min(
dp(s1, i, s2, j - 1) + 1,
dp(s1, i - 1, s2, j) + 1,
dp(s1, i - 1, s2, j - 1) + 1
);
}
return memo[i][j];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
动态规划解法2，子问题叠加：
int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]
int[][] dp = new int[m + 1][n + 1];
// base case
for (int i = 1; i <= m; i++)
dp[i][0] = i;
for (int j = 1; j <= n; j++)
dp[0][j] = j;
// 自底向上求解
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
);
}
}
}
// 储存着整个 s1 和 s2 的最小编辑距离
return dp[m][n];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
53、最大子数组和
我们每次写自己的代码的时候，无比的清晰知道自己要做什么，每一行代码都有什么作用，怎么才能输出自己想要的结果
所以我们看别人的代码也应该是要达到这个效果才行
所以是 思路——》 大致的代码逻辑 ——》生成代码
说实话，我不太理解这个题是怎么用滑动窗口的，这个题目的动态规划解法也和之前的很不一样，并非是通过dp[i-1]推出dp[i]，而是以 nums[i] 为结尾的「最大子数组和」为 dp[i]。
所以最后的结果要对dp数组进行遍历，才能获取最大值
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
int[] dp = new int[n];
// base case
// 第一个元素前面没有子数组
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// 得到 nums 的最大子数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
滑动窗口：（滑动窗口算法就是专门处理子串/子数组问题的）
双指针都是从左边0开始的，right往外扩，left缩小窗口
所以重点是找到外扩条件和缩小条件？以及什么时候更新答案？
在窗口内元素之和大于等于 0 时扩大窗口，在窗口内元素之和小于 0 时缩小窗口，在每次移动窗口时更新答案
在理解动态规划的思路之后再去看这个滑动窗口的答案就容易很多了，有几个注意点：
首先是这个更新答案是通过一个单独的变量maxSum，保存最大的加和数值
其次是缩小窗口的条件，是通过一个while循环，如果窗口记录的加和数值windowSum<0，则增加left，缩小窗口，一直到windowSum>=0
int maxSubArray(int[] nums) {
int left = 0, right = 0;
int windowSum = 0, maxSum = Integer.MIN_VALUE;
while(right < nums.length){
// 扩大窗口并更新窗口内的元素和
windowSum += nums[right];
right++;
// 更新答案
maxSum = windowSum > maxSum ? windowSum : maxSum;
// 判断窗口是否要收缩
while(windowSum < 0) {
// 缩小窗口并更新窗口内的元素和
windowSum -= nums[left];
left++;
}
}
return maxSum;
}
总结是大于做新的题目的、、、量到一定时就要进行总结，才可以加速质变、、、
1143、最长公共子序列
这道题是我首次独立使用动态规划去分析问题去解决问题，只有真正自己去动手才能增加能力
很明显是用二维数组去做记录，根据已有的二维数组去推出下一个元素的数值时，但是我这个规律掌握的并不是很好，自己就乱了，每个二位数组的元素的含义是不清晰的，变化规律掌握的也是模糊的，存在重复记录的问题，本质还是含义不清晰、、
看来动态规划难点在这里啊、、、
虽然解题垃圾的一匹，但还是有收获的
代码
class Solution {
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
int[][] dp = new int[m + 1][n + 1];
// 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
// base case: dp[0][..] = dp[..][0] = 0
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 现在 i 和 j 从 1 开始，所以要减一
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// s1[i-1] 和 s2[j-1] 必然在 lcs 中
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
}
583. 两个字符串的删除操作
class Solution {
public int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 复用前文计算 lcs 长度的函数
int lcs = longestCommonSubsequence(s1, s2);
return m - lcs + n - lcs;
}
// 计算最长公共子序列的长度
int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 现在 i 和 j 从 1 开始，所以要减一
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// s1[i-1] 和 s2[j-1] 必然在 lcs 中
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
}
// 详细解析参见：
// https://labuladong.gitee.io/article/?qno=
