开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【学习笔记】【Leetcode 分门别类讲解】——动态规划 -> 正文阅读

[数据结构与算法]【学习笔记】【Leetcode 分门别类讲解】——动态规划

在这里插入图片描述

动规五部曲

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

基础题目

【509. 斐波那契数】

在这里插入图片描述

class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=1;
        for(int i = 2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列

class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=1;
        for(int i = 2;i<=n;i++){
            //dp[i]=dp[i-1]+dp[i-2];
            int sum = dp[0]+dp[1];
            dp[0]=dp[1];
            dp[1]=sum;
        }
        return dp[1];
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

当然也可以递归

class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
        return fib(n-1)+fib(n-2);
    }
};

时间复杂度：O(2^n)
空间复杂度：O(n) 算上了编程语?中实现递归的系统栈所占空间

【70. 爬楼梯】

1. 确定dp数组（dp table）以及下标的含义： dp[i]：爬到第i层楼梯，有dp[i]种?法

2. 确定递推公式： 上i层楼，先看上i-1层楼有dp[i-1]种方法，上i-2层楼有dp[i-2]种方法，那么dp[i]就是=dp[i-1]+dp[i-2]

3. dp数组如何初始化: 要明确dp的含义，dp[0]没意义，所以从dp[1]开始定义

4. 确定遍历顺序： 从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序?定是从前向后遍历的

5. 举例推导dp数组 n=5，1 2 3 5 8

class Solution {
public:
    int climbStairs(int n) {
        if(n<3) return n;
        vector<int> dp(n+1);
        dp[1]=1;
        dp[2]=2;
        for(int i = 3;i<n+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

——拓展：绝佳的???试题（完全背包问题）

这道题?还可以继续深化，就是?步?个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种?法爬到n阶楼顶。
这?有难度了，这其实是?个完全背包问题，装满背包的方法
在这里插入图片描述

【746. 使用最小花费爬楼梯】

1. 确定dp数组（dp table）以及下标的含义： dp[i]的定义：到达第i个台阶所花费的最少体?为dp[i]

2. 确定递推公式： dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

3. dp数组如何初始化: dp[0] = cost[0]; dp[1] = cost[1];

4. 确定遍历顺序： 从前到后遍历cost数组就可以了

5. 举例推导dp数组
在这里插入图片描述

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size(),0);
        dp[0]=cost[0];
        dp[1]=cost[1];
        for(int i = 2;i<cost.size();i++){
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
        int res = min(dp[cost.size()-1],dp[cost.size()-2]);
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

【62. 不同路径】

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
想要求dp[i][j]，只能有两个?向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]，所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
for (int i = 0; i < m; i++) dp[i][0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1;
dp[i][j]都是从其上?和左?推导?来，那么从左到右?层?层遍历就可以了。

在这里插入图片描述

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i = 0;i<m;i++) dp[i][0]=1;
        for(int j = 0;j<n;j++) dp[0][j]=1;
        for(int a = 1;a<m;a++){
            for(int b =1;b<n;b++){
                dp[a][b] = dp[a-1][b]+dp[a][b-1];
            }
        }
        return dp[m-1][n-1];
    }
};

时间复杂度：O(m * n)
空间复杂度：O(m * n)

【63. 不同路径II】

有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。
1.dp[i]含义不变
2.递推公式不变，多个判断条件：(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）
3.初始化：

vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

注意代码?for循环的终?条件，?旦遇到obstacleGrid[i][0] == 1的情况就停?dp[i][0]的赋值1的操作，dp[0][j]同理

4.从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出，?定是从左到右?层?层遍历，这样保证推导
dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]?定是有数值。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i = 0;i<m && obstacleGrid[i][0]==0;i++){dp[i][0]=1;}
        for(int j = 0;j<n && obstacleGrid[0][j]==0;j++){dp[0][j]=1;}
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                if(obstacleGrid[i][j]==1) continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

【343. 整数拆分】

1.dp[i]：分拆数字i，可以得到的最?乘积为dp[i]。
2.?个是j * (i - j) 直接相乘 ; ?个是j * dp[i - j]，相当于是拆分(i - j)
递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));——前面这个max是为了记录整体的max以至于可以一直更新max
3.只初始化dp[2] = 1

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2]=1;
        for(int i = 3;i<=n;i++){
            for(int j = 1;j<i-1;j++){
                dp[i] = max(dp[i],max(j*dp[i-j],j*(i-j)));
            }
        }
        return dp[n];
    }
};

【96. 不同的二叉搜索树】

在这里插入图片描述
2.递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左?树节点数量，i-j 为以j为头结点右?树节点数量
3.空节点也是?颗?叉树，也是?颗?叉搜索树所以初始化dp[0] = 1

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0]=1;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=i;j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
};

背包问题——01背包

【01背包理论基础】

有N件物品和?个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每
件物品只能??次，求解将哪些物品装?背包?物品价值总和最?。

在这里插入图片描述

—— ?维dp数组，都记录

1.dp[i][j] 表示从下标为[0-i]的物品?任意取，放进容量为j的背包，价值总和最?是多少
在这里插入图片描述
3.初始化
4.遍历顺序：先物品再背包好理解，反过来也可以，因为递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上??向（包括正左和正上两个?向）

void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 二维数组
    vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));

    // 初始化 
    for (int j = bagWeight; j >= weight[0]; j--) {
        dp[0][j] = dp[0][j - weight[0]] + value[0];
    }

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        }
    }

    cout << dp[weight.size() - 1][bagWeight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

—— 一维dp滚动数组，覆盖

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

于其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
递推公式：相对于二维dp数组的写法，就是把dp[i][j]中i的维度去掉了：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
初始化:如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。
遍历顺序：二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
倒叙遍历是为了保证物品i只被放入一次！

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}

—— 总结可能是面试题

要求先实现?个纯?维的01背包，如果写出来了，然后再问为什么两个for循环的嵌套顺序这么写？反过来写?不?？再讲?讲初始化的逻辑。
然后要求实现?个?维数组的01背包，最后再问，?维数组的01背包，两个for循环的顺序反过来写?不?？为什么？

【416. 分割等和子集】

01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]i，价值也是nums[i]，背包体积是sum/2。

dp[i]表示背包总容量是i，最?可以凑成i的?集总和为dp[i]。
本题，相当于背包?放?数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

 // 题?中说：每个数组中的元素不会超过 100，数组的??不会超过 200
 // 总和不会?于20000，背包最?只需要其中?半，所以10001??就可以了
 vector<int> dp(10001, 0);

// 开始 01背包 
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}

在这里插入图片描述

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 那么背包内总和不会大于20000，所以定义一个20000大的数组。
        vector<int> dp(20001, 0); 
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包 
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target 
        if (dp[target] == target) return true;
        return false;      
    }
};

【1049. 最后?块石头的重量 II】

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
本题物品的重量为store[i]，物品的价值也为store[i]。

dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
vector dp(15001, 0);

for (int i = 0; i < stones.size(); i++) { // 遍历物品
    for (int j = target; j >= stones[i]; j--) { // 遍历背包
        dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}

在这里插入图片描述

【494. 目标和】

回溯会超时，转化为01背包问题

假设加法的总和为S，那么减法对应的总和就是sum - S。
所以我们要求的是 S - (sum - S) = target
S = ( target + sum) / 2
此时问题就转化为，装满容量为S背包，有?种?法。

dp[j] 表示：填满j（包括j）这么?容积的包，有dp[j]种?法；
递推式：dp[j] = dp[j]+dp[j-nums[i]]；看下图联系硬币来理解：遍历物品1时，填满4有本来遍历0的dp[4]总方法，再加上现在遍历到1时dp[4-nums[1]]种方法。所以是+=；硬币更好理解：填满总金额为5，只有物品0时方法为dp[5]，现在遍历到物品1，自然是前面只有0的dp[5]+现在有了1的dp[5-coins[1]]；
初始化：dp[0]=1.不然后面没法算，理解为填满0只有一种办法就是啥也不装
遍历顺序：先物品再背包

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int i = 0;i<nums.size();i++) sum += nums[i];
        if((sum + target) % 2==1) return 0;// 此时没有?案
        if (target > sum) return 0; // 此时没有?案
        int S = (target + sum) / 2;//
        vector<int> dp(S+1,0);
        dp[0]=1;
        for(int i = 0;i<nums.size();i++){
            for(int j = S;j>=nums[i];j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[S];
    }
};

【474.?和零】

背包问题——完全背包

有N件物品和?个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件
物品都有?限个（也就是可以放?背包多次），求解将哪些物品装?背包?物品价值总和最?。
完全背包和01背包问题唯?不同的地?就是，每种物品有?限件。

【518. 零钱兑换 II】

本题和纯完全背包不?样，纯完全背包是能否凑成总?额，?本题是要求凑成总?额的个数！

dp[j]：凑成总?额j的货币组合数为dp[j]
求装满背包有?种?法，?般公式都是：dp[j] += dp[j - nums[i]];
所以递推公式：dp[j] += dp[j - coins[i]];
?先dp[0]?定要为1，dp[0] = 1是递归公式的基础。
从dp[i]的含义上来讲就是，凑成总?额0的货币组合数为1。
下标?0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount +1,0);
        dp[0]=1;
        for(int i = 0;i<coins.size();i++){
            for(int j = coins[i];j<=amount;j++){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

【377. 组合总和 Ⅳ】

dp[i]: 凑成?标正整数为i的排列个数为dp[i]
dp[i] += dp[i - nums[j]];
dp[0] = 1 于?0下标的dp[i]初始化为0
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,0);
        dp[0] = 1;
        for(int j = 0;j<=target;j++){
            for(int i = 0;i<nums.size();i++){
                if(j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]) {
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
};

【70. 再爬?次楼梯】

改为：?步?个台阶，两个台阶，三个台阶，…，直到 m个台阶。问有多少种不同的?法可以爬到楼顶呢？
1阶，2阶，… m阶就是物品，楼顶就是背包。
每?阶可以重复使?，例如跳了1阶，还可以继续跳1阶。
问跳到楼顶有?种?法其实就是问装满背包有?种?法。
此时?家应该发现这就是?个完全背包问题了！

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int j = 1;j<=n;j++){// 遍历背包
            for(int i = 1;i<=m;i++){// 遍历物品
                if(j>=i) dp[j] += dp[j-i];
            }
        }
        return dp[n];
    }
};

代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了。

【322. 再兑换?次零钱】

dp[j]：凑?总额为j所需钱币的最少个数为dp[j]
得到dp[j]（考虑coins[i]），只有?个来源，dp[j - coins[i]]（没有考虑coins[i]）。
凑?总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上?个钱币coins[i]即dp[j - coins[i]] +1就是dp[j]
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最?的。
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;

本题求钱币最?个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最?个数。。
所以本题并不强调集合是组合还是排列

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i = 0;i<coins.size();i++){
            for(int j = coins[i];j<=amount;j++){ // 如果dp[j - coins[i]]是初始值则跳过
                if (dp[j - coins[i]] != INT_MAX)    dp[j] = min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

【279.再一次完全平?数】

把题?翻译?下：完全平?数就是物品（可以?限件使?），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
多么浓厚的完全背包氛围啊，感受一下

dp[i]：和为i的完全平?数的最少数量为dp[i]
dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
此时我们要选择最?的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

在这里插入图片描述

【139.单词拆分】

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使?字典中的单词，说明就是?个完全背包！

dp[i] : 字符串?度为i，dp[i]为true，表示可以拆分为?个或多个在字典中出现的单词。
递推：dp[i]怎么来：如果确定dp[j] 是true，且 [j, i] 这个区间的?串出现在字典?，那么dp[i]?定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的?串出现在字典? && dp[j]是true) 那么 dp[i] = true。
dp[0]?定要为true，否则递归下去后?都都是false了
本题最终要求的是是否都出现过，所以对出现单词集合?的元素是组合还是排列，并不在意！
那么本题使?求排列的?式，还是求组合的?式都可以。
但本题还有特殊性，因为是要求?串，最好是遍历背包放在外循环，将遍历物品放在内循环。
如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的?串都预先放在?个容器?

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());//为了find
        vector<bool> dp(s.size()+1,0);
        dp[0]=1;
        for(int i = 1;i<=s.size();i++){// 遍历背包
            for(int j = 0;j<i;j++){// 遍历物品
                string word = s.substr(j,i-j);//substr(起始位置，截取的个数)
                if(wordSet.find(word)!=wordSet.end() && dp[j]==1) dp[i]=1;
            }
        }
        return dp[s.size()];
    }
};

时间复杂度：O(n^3)，因为substr返回?串的副本是O(n)的复杂度（这?的n是substring的?度）
空间复杂度：O(n)

背包问题总结篇

——主要是递推公式和遍历顺序

在这里插入图片描述

打家劫舍

【198.打家劫舍】——不能连续

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的?额为dp[i]。
决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房?定是不考虑的，找出下标i-2（包括i-2）
以内的房屋，最多可以偷窃的?额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这?是考虑，并不是?定要偷i-1房，这是
很多同学容易混淆的点）
然后dp[i]取最?值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i = 2;i<nums.size();i++){
            dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.size()-1];
    }
};

【213.打家劫舍II】——首尾成环

首尾成环了，所以要分开考虑

class Solution {
public:
    int robslide(vector<int>& nums,int start,int end){
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start+1] = max(nums[start],nums[start+1]);
        for(int i = start+2;i<=end;i++){
            dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[end];
    }
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int res1 = robslide(nums,0,nums.size()-2);
        int res2 = robslide(nums,1,nums.size()-1);
        return max(res1,res2);
    }
};

【337.打家劫舍 III】——二叉树

在这里插入图片描述
== 本题?定是要后序遍历，因为通过递归函数的返回值来做下?步计算。==
与198.打家劫舍，213.打家劫舍II?样，关键是要讨论当前节点抢还是不抢。
如果抢了当前节点，两个孩?就不是动，如果没抢当前节点，就可以考虑抢左右孩?（注意这?说的
是“考虑”）

这?我们要求?个节点偷与不偷的两个状态所得到的?钱，那么返回值就是?个?度为2的数组。
参数为当前节点，代码如下：

vector<int> robTree(TreeNode* cur) {

	所以dp数组以及下标的含义：下标为0记录不偷该节点所得到的的最??钱，下标为1记录偷该节点所得到的的最??钱。
	所以本题dp数组就是?个?度为2的数组！

在遍历的过程中，如果遇到空节点的话，很明显，?论偷还是不偷都是0，所以就返回
if (cur == NULL) return vector<int>{0, 0};
这也相当于dp数组的初始化
遍历顺序

// 下标0：不偷，下标1：偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右
// 中

确定单层递归的逻辑【看eg图理解】
如果是偷当前节点，那么左右孩?就不能偷，val1 = cur->val + left[0] + right[0];
如果不偷当前节点，那么左右孩?就可以偷，?于到底偷不偷?定是选?个最?的，
所以：val2 =max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最??钱，偷当前节点得到的最??钱}

class Solution {
public:
    vector<int> robTree(TreeNode* cur){
        if(cur==nullptr) return vector<int>{0,0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        //偷cur
        int res1 = cur->val+left[0]+right[0];
        //不偷cur
        int res2 = max(left[0],left[1])+max(right[0],right[1]);
        return {res2,res1};
    }
    int rob(TreeNode* root) {
        vector<int> dp = robTree(root);
        return max(dp[0],dp[1]);
    }
};

买卖股票的最佳时机

【121. 最佳时机】——只有一笔买卖

股票问题的方法就是 动态规划，因为它包含了重叠子问题，即买卖股票的最佳时机是由之前买或不买的状态决定的，而之前买或不买又由更早的状态决定的…

由于本题只有一笔交易（买入卖出），因此除了动态规划，我们还可以使用更加简便的方法实现。

方法一：一次遍历
遍历一遍数组，计算每次到当天为止的最小股票价格和最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice = int(1e9);
        int maxprofit = 0;
        for (auto price : prices){
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(minprice, price);
        }
        return maxprofit;
    }
};

时间复杂度：O(n)，遍历了一遍数组。
空间复杂度：O(1)，使用了有限的变量。

方法二：动态规划（一维dp数组简单写法）

其实方法一的思路不是凭空想象的，而是由动态规划的思想演变而来。这里介绍一维动态规划思想。

dp[i]表示前 i 天的最大利润，因为我们始终要使利润最大化，则：

dp[i] = max(dp[i-1], prices[i]-minprice)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0; // 边界条件
        int minprice = prices[0];
        vector<int> dp (n, 0);

        for (int i = 1; i < n; i++){
            minprice = min(minprice, prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - minprice);
        }
        return dp[n - 1];
    }
};

时间复杂度：O(n)。
空间复杂度：O(n)。

方法二：动态规划（二维dp数组写法）【看eg图分析】

【系统动态规划】

dp[i][0] 表示第i天持有股票所得现?。
dp[i][1] 表示第i天不持有股票所得现?。

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现?就是昨天持有股票的所得现? 即：dp[i - 1][0]
第i天买?股票，所得现?就是买?今天的股票后所得现?即：-prices[i]
所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]，也可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现?就是昨天不持有股票的所得现? 即：dp[i - 1][1]
第i天卖出股票，所得现?就是按照今天股票佳价格卖出后所得现?即：prices[i] + dp[i - 1][0]
所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n==0) return 0;
        vector<vector<int>> dp(n,vector<int>(2,0));
        //dp[i][0] 持有股票时最大现金
        //dp[i][1] 不持有股票时最大现金
        dp[0][0] = -prices[0];//买入初始化
        dp[0][1] = 0;
        for(int i = 1;i<n;i++){
            dp[i][0] = max(dp[i-1][0],-prices[i]);
            dp[i][1] = max(dp[i-1][1],prices[i]+dp[i][0]);
        }
        return dp[n-1][1];
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

【122.最佳时机II】——可以买卖多次

本题和121的唯?区别本题股票可以买卖多次了（注意只有?只股票，所以再次购买前要出售掉之前的股票）
在动规五部曲中，这个区别主要是体现在递推公式上，其他都和121. 买卖股票的最佳时机?样?样的。
在121中，因为股票全程只能买卖?次，所以如果买?股票，那么第i天持有股票即dp[i][0]?定就是 -prices[i]。
?本题，因为?只股票可以买卖多次，所以当第i天买?股票的时候，所持有的现?可能有之前买卖过的利润
这个利润就是前一只股票卖出的价格dp[i - 1][1]，再减去第i天买入的股票的价格，就是第i天所持有的现?
即：dp[i - 1][1] - prices[i]。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n==0) return 0;
        vector<vector<int>> dp(n,vector<int>(2,0));
        //dp[i][0] 持有股票时最大现金
        //dp[i][1] 不持有股票时最大现金
        dp[0][0] = -prices[0];//买入初始化
        dp[0][1] = 0;
        for(int i = 1;i<n;i++){
            dp[i][0] = max(dp[i-1][0],-prices[i]+dp[i - 1][1] );
            dp[i][1] = max(dp[i-1][1],prices[i]+dp[i][0]);
        }
        return dp[n-1][1];
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

【123. 最佳时机 III】——最多两笔买卖

一. ?天?共就有五个状态，
0. 没有操作
1. 第?次买?
2. 第?次卖出
3. 第?次买?
4. 第?次卖出
dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最?现?。

二. 递推公式
达到dp[i][1]状态，有两个具体操作：

操作?：第i天买?股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
操作?：第i天没有操作，?是沿?前?天买?的状态，即：dp[i][1] = dp[i - 1][1]

所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

操作?：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作?：第i天没有操作，沿?前?天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分：
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

三. 初始化
dp[0][0]=0;//无操作
dp[0][1]=-prices[0];//第一次买入
dp[0][2]=0;//第一次卖出，利润初始化为0，后续取max，取比其大（利润都是>=0的）
dp[0][3]=-prices[0]//第二次买入，不?管第?次，现在?头上没有现?，只要买?，现?就做相应的减少。
dp[0][4]=0;
在这里插入图片描述

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        vector<vector<int>> dp(prices.size(),vector<int>(5,0));
        dp[0][1]=-prices[0];
        dp[0][3]=-prices[0];
        for(int i = 1;i<prices.size();i++){
            dp[i][0]=dp[i-1][0];//不操作
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);//第一次买入
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);//第一次卖出
            dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);//第二次买入
            dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);//第二次卖出
        }
        return dp[prices.size()-1][4];
    }
};

时间复杂度：O(n)
空间复杂度：O(n * 5)

【188. 最佳时机 IV】——最多k笔买卖

除了0以外，偶数就是卖出，奇数就是买?。题?要求是?多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));
        for(int i = 1;i<2*k;i+=2){
            dp[0][i]=-prices[0];
        }
        for(int i = 1;i<prices.size();i++){
            for(int j = 0;j<2*k-1;j+=2){
                dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i]);//买入
                dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);//卖出
            }
        }
        return dp[prices.size()-1][2*k];
    }
};

【309.最佳时机含冷冻期】——买卖多次，卖出一天有冷却

状态0：买?股票状态（今天买?股票，或者是之前就买?了股票然后没有操作）
卖出股票状态，这?就有两种卖出股票状态
状态1：两天前就卖出了股票，度过了冷冻期，?直没操作，今天保持卖出股票状态
状态2：今天卖出了股票
状态3：今天为冷冻期状态，但冷冻期状态不可持续，只有?天！
初始化：
dp[0][0]=-prices[0];
递推：
- dp[i][0]怎么来的：
  前一天如果已经买入股票，保持：dp[i-1][0];
  今天买，分为两种情况：
  1：昨天是冷却期，今天买入手上的钱：dp[i-1][3]-prices[i]
  2：昨天是状态1，dp[i-1][1]-prices[i]
  所以dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));
- dp[i][1]怎么来的：
  肯定有个保持：dp[i-1][1];
  昨天是冷却期：dp[i-1][3]；
  dp[i][1]=max(dp[i-1][1],dp[i-1][3]);
- dp[i][2]怎么来的
  dp[i][2]=dp[i-1][0]+prices[i];
- dp[i][3]怎么来的
  dp[i][3]=dp[i-1][2];

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(prices.size()==0) return 0;
        vector<vector<int>> dp(prices.size(),vector<int>(4,0));
// 状态0：买?股票状态（今天买?股票，或者是之前就买?了股票然后没有操作）
// 卖出股票状态，这?就有两种卖出股票状态
    // 状态1：两天前就卖出了股票，度过了冷冻期，?直没操作，今天保持卖出股票状态
    // 状态2：今天卖出了股票
// 状态3：今天为冷冻期状态，但冷冻期状态不可持续，只有?天！
        dp[0][0]=-prices[0];
        for(int i = 1;i<prices.size();i++){
            dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));
            dp[i][1]=max(dp[i-1][1],dp[i-1][3]);
            dp[i][2]=dp[i-1][0]+prices[i];
            dp[i][3]=dp[i-1][2];
        }
        return max(dp[n - 1][3],max(dp[n - 1][1], dp[n - 1][2]));
    }
};

【714. 最佳时机含手续费】——买卖多次，每次有手续费

相对于动态规划：122.买卖股票的最佳时机II，本题只需要在计算卖出操作的时候减去?续费就可以了，代码?乎是?样的。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size()==0) return 0;
        vector<vector<int>> dp(prices.size(),vector<int>(2,0));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i = 1;i<prices.size();i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
        }
        return dp[prices.size()-1][1];
    }
};

子序列问题

【300. 最长递增子序列】

dp[i]表示
以 nums[i] 结尾的「上升子序列」的长度。注意： nums[i] 必须被选取，且必须是这个子序列的最后一个元素；
状态转移?程
位置i的最?升序?序列等于j从0到i-1各个位置的最?升序?序列 + 1 的最?值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这?不是要dp[i] 与 dp[j] + 1进??较，?是我们要取dp[j] + 1的最?值。
dp[i]的初始化
每?个i，对应的dp[i]（即最?上升?序列）起始???少都是是1.
确定遍历顺序
dp[i] 是有0到i-1各个位置的最?升序?序列推导?来，那么遍历i?定是从前向后遍历。
j其实就是0到i-1，遍历i的循环?外层，遍历j则在内层，代码如下：

注意不能返回最后一个状态值，最后一个状态值只表示以 nums[len - 1] 结尾的「上升子序列」的长度，状态数组 dp 的最大值才是题目要求的结果。一定要有个res记录最大值，dp[size-1]不一定是最大值

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(),1);
        int res = 0;//用来记录最大值所在位置，一定要有个res记录最大值，dp[size-1]不一定是最大值
        for(int i = 1;i<nums.size();i++){
            for(int j = 0;j<i;j++){
                if(nums[i]>nums[j]) dp[i] = max(dp[i],dp[j]+1);
            }
            if(dp[i]>res) res = dp[i];
        }
        return res;
    }
};

【674. 最长连续递增序列】

和【300. 最长递增子序列】差别就在要找连续的子序列

dp[i]:
以 nums[i] 结尾的「连续上升子序列」的长度。注意： nums[i] 必须被选取，且是这个子序列的最后一个元素；
递推：
if(nums[i+1]>nums[i]) dp[i+1] = dp[i]+1;
初始化：
dp[i]=1;
同样要注意的是最后那个dp不一定是最大的，所以要一个res来记录最大值

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        int res = 1;
        if(n<=1) return n;
        vector<int> dp(n,1);
        for(int i = 0;i<n-1;i++){
            if(nums[i+1]>nums[i]) dp[i+1]=dp[i]+1;
            if(dp[i+1]>res) res=dp[i+1];
        }
        return res;
    }
};

【718. 最长重复子数组】

dp[i][j] ：长度为i，末尾项为A[i-1]的子数组，与长度为j，末尾项为B[j-1]的子数组，二者的最大公共后缀子数组长度
如果 A[i-1] == B[j-1] ，有 dp[i][j] = dp[i-1][j-1] + 1
根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
但dp[i][0] 和dp[0][j]要初始值，因为为了?便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
所以dp[i][0] 和dp[0][j]初始化为0。

在这里插入图片描述

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        int res = 0;
        for(int i = 1;i<=nums1.size();i++){
            for(int j = 1;j<=nums2.size();j++){
                if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                if(dp[i][j]>res) res = dp[i][j];
            }
        }
        return res;
    }
};

时间复杂度O(n * m) n 为A?度，m为B?度
空间复杂度O(n * m)
在这里插入图片描述
此时遍历nums2数组的时候，就要从后向前遍历，这样避免重复覆盖。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<int> dp(vector<int>(nums2.size() + 1, 0));
        int res = 0;
        for(int i = 1;i<=nums1.size();i++){
            for(int j = nums2.size();j>=1;j--){
                if(nums1[i-1]==nums2[j-1]) dp[j]=dp[j-1]+1;
                else dp[j] = 0; // 注意这?不相等的时候要有赋0的操作
                if(dp[j]>res) res = dp[j];
            }
        }
        return res;
    }
};

时间复杂度O(n * m) n 为A?度，m为B?度
空间复杂度O(m)

【1143. 最长公共子序列】——总算是自己磕出来了

首先它是子序列问题，
参考【300. 最长递增子序列】dp[i]：以 nums[i] 结尾的「上升子序列」的长度。注意： nums[i] 必须被选取，且必须是这个子序列的最后一个元素；
这题有两个序列，再参考【718. 最长重复子数组】：所以是dp[i][j] ：长度为i，末尾项为A[i-1]的子序列，与长度为j，末尾项为B[j-1]的子序列，二者的最长公共子序列长度
递推公式：如果 A[i-1] == B[j-1] ，有 dp[i][j] = dp[i-1][j-1] + 1，不同点在于A[i-1] ！= B[j-1]时，注意dp[i][j]的含义是二者的最长公共子序列长度，所以是max(dp[i][j-1],dp[i-1][j]);

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //dp[i][j]表示[0,i-1]的A和[0,j-1]的B最长的公共子序列 的长度
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
        for(int i = 1;i<=text1.size();i++){
            for(int j = 1;j<=text2.size();j++){
                if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

【1035. 不相交的线】

——和【1143. 最长公共子序列】不能说一模一样，只能说完全一致

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        for(int i = 1;i<=nums1.size();i++){
            for(int j = 1;j<=nums2.size();j++){
                if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] =max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

【53. 最大子序和】

——需要注意的是int res = nums[0];

dp[i]：包括下标i之前的最?连续?序列和为dp[i]
dp[i+1]=max(nums[i+1],nums[i+1]+dp[i]);
dp[0] = nums[0]

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        vector<int> dp(nums.size(),0);
        dp[0]=nums[0];
        int res = nums[0];
        for(int i = 0;i<nums.size()-1;i++){
            dp[i+1]=max(nums[i+1],nums[i+1]+dp[i]);
            if(dp[i+1]>res) res = dp[i+1];
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

【392. 判断子序列】——编辑距离的题?最能体现出动规精髓和巧妙之处，还没体会到

和【1143. 最长公共子序列】很像，可以用其函数来判断return的res是不是==s.size()；当然，这题还可以更简单点，因为这题要求的是相同的子序列，所以 if(s[i-1]！=t[j-1]) dp[i][j]=dp[i][j-1];不需要多判断上方的
在这里插入图片描述

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size()>t.size()) return false;
        else if(s.size()==t.size() && s!=t) return false;
        else{
            vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
            for(int i = 1;i<=s.size();i++){
                for(int j = 1;j<=t.size();j++){
                    if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                    else dp[i][j]=dp[i][j-1];
                }
            }
            return dp[s.size()][t.size()]==s.size();
        }
    }
};

【115.不同的子序列】

在这里插入图片描述

dp[i][j]：以i-1为结尾的s?序列中出现以j-1为结尾的t的个数为dp[i][j]
所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有?部分组成，不?s[i - 1]来匹配，即：dp[i - 1][j]
所以递推公式为：dp[i][j] = dp[i - 1][j];
随着递归压栈，子问题规模（子串长度）在变小：
小到 t 变成空串，此时 s 为了匹配它，方式只有1种：一个字符都不挑。（或 s 也是空串，什么都不做就匹配了，方式数也是1）
小到 s 变成空串，但 t 不是，s 怎么也匹配不了 t，方式数为 0
递归函数的参数可以传子串或索引，但用索引描述子问题，不用每次都做切割，也更容易迁移到 dp 解法。

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(t.size()+1,vector<uint64_t>(s.size()+1,0));
        for(int i = 0;i<s.size();i++) dp[0][i]=1;
        for(int j = 1;j<t.size();j++) dp[j][0]=0;
        for(int i = 1;i<=s.size();i++){
            for(int j = 1;j<=t.size();j++){
                if(s[i-1]==t[j-1]) dp[j][i]=dp[j-1][i-1]+dp[j][i-1];
                else dp[j][i] = dp[j][i-1];
            }
        }
        return dp[t.size()][s.size()];
    }
};

这里把这个图反过来看，习惯长度小的在下面了

【583. 两个字符串的删除操作】

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除i个元素才能和word2相同;dp[0][j]的话同理

在这里插入图片描述

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i = 1;i<=word1.size();i++) dp[i][0]=i;
        for(int j = 1;j<=word2.size();j++) dp[0][j]=j;
        for(int i = 1;i<=word1.size();i++){
            for(int j = 1;j<=word2.size();j++){
                if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

【72. 编辑距离】——增删改好好理解下

dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最少需要操作的次数（相较于【583】除了删除操作，这题还有增加和修改）
增，dp[i][j] = dp[i][j - 1] + 1
删，dp[i][j] = dp[i - 1][j] + 1
改，dp[i][j] = dp[i - 1][j - 1] + 1
自然是取min
初始化同【583】，dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除（增删改都可以）i个元素才能和word2相同

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i = 1;i<=word1.size();i++) dp[i][0]=i;
        for(int j = 1;j<=word2.size();j++) dp[0][j]=j;
        for(int i = 1;i<=word1.size();i++){
            for(int j = 1;j<=word2.size();j++){
                if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j] = min({dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

【647. 回文子串】

布尔类型的dp[i][j]：表示[i,j]内（注意是左闭右闭）的?串是否是回??串，如果是dp[i][j]为true，否则为false。
整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

【516. 最长回文子序列】

dp[i][j]：字符串s在[i, j]范围内最?的回??序列的?度为dp[i][j]。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for(int i = 0;i<s.size();i++) dp[i][i]=1;
        for(int i = s.size()-1;i>=0;i--){
            for(int j = i+1;j<s.size();j++){
                if(s[i]==s[j]){
                    dp[i][j] = dp[i+1][j-1]+2;
                }
                else{
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.size()-1];
    }
};