[数据结构与算法] 动态规划专题讲解

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

-> 数据结构与算法 -> 动态规划专题讲解 -> 正文阅读

[数据结构与算法]动态规划专题讲解

6. 动态规划

复现代码随想录DP专题

代码随想录 (programmercarl.com)

卡尔哥的文章真的很好，思路十分清晰，我照着他的路线，把他提及的题目刷了一遍，也写了点自己的理解，仅供参考。

一、套路

动态规划五部曲

确定dp数组以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
打印数组（与自己的推导比较，看哪里错了）

二、DP基础

1. 斐波那契数（LeetCode-509）

题目

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

思路

这题很简单，我试着用五部曲练练手

dp[i] 的意义为：第 i 个数的斐波那契数值为 dp[i]
$d p [i] = d p [i ? 1] + d p [i ? 2]$ ?
dp[0]=0 dp[1]=1
根据递推公式可知，dp[i] 依赖它的前两个元素，所以一定是从前往后遍历
推导一下前十项 0 1 1 2 3 5 8 13 21 34 55

代码展示

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

但其实还可以优化，因为dp[i] 只依赖它的前两个元素，只需维护两个元素，没有必要写出整个数组，浪费了空间

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

2. 爬楼梯（LeetCode-70）

题目

假设你正在爬楼梯。需要 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 阶

思路

第?层楼梯再跨两步就到第三层，第?层楼梯再跨?步就到第三层。所以到第三层楼梯的状态可以由第?层楼梯和到第?层楼梯状态推导出来

五部曲

dp[i] 定义：爬到第 i 阶有 dp[i] 种方法
$d p [i] = d p [i ? 2] + d p [i ? 1]$ ?
dp[1]=1 dp[2]=2 正整数不用考虑 dp[0]
肯定从前往后
前五项 1 2 3 5 8

代码展示

class Solution
{
public:
    int climbStairs(int n)
    {
        // 这步忘记了，导致n=1时访问不到dp[2]
        if (n<=1)
        {
            return n;
        }  
        vector<int> dp(n + 1);
        dp[1] = 1, dp[2] = 2;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
            cout << dp[i];
        }
        return dp[n];
    }
};

也是可以优化，滚动数组优化空间

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

3. 使用最小花费爬楼梯（LeetCode-746）

题目

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

2 <= cost.length <= 1000
0 <= cost[i] <= 999

思路

五部曲

定义：爬到第 i 个台阶的最低花费为 dp[i]
当前台阶的最低花费与 i-1 和 i-2 台阶有关，应该是从（ i-1 台阶最低消费+从 i-1 台阶向上爬的费用）和（i-2 台阶最低消费+从 i-2 台阶向上爬的费用）中取较小值
$d p [i] = m i n ((d p [i ? 1] + c o s t [i ? 1]), (d p [i ? 2] + c o s t [i ? 2]))$
初始值 dp[0]=0 dp[1]=0
显然从前往后
示例一应该是 dp[N]={0,0,10,15}

代码展示

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

这题还是可以滚动数组优化

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

4. 不同路径（LeetCode-62）

题目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

思路

五部曲继续

dp[m][n] 含义：到达m行n列有 dp[m][n] 条路径
机器人每次只能向下或向右移动，所以该点路径条数只与它上面和左边的点有关，是它们路径条数之和
$d p [m] [n] = d p [m ? 1] [n] + d p [m] [n ? 1]$
初始化时，最左边一列和最上面一行的值肯定为1
要先有 $? 1$ 才能有你，肯定正序
略

代码展示

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

可以滚动数组优化，可以看出，我们计算是以行为单位一行一行计算的，其实该点值只和它上一行有关，所以创建一个长度为网格列数的数组
$d p [j] = d p [j] + d p [j ? 1]$
dp[j-1] 最初是欲计算点上左侧的值，被计算后，数值的含义下移，变成欲计算点左侧的值。同理 dp[j] 在计算之前代表欲计算点上侧的值

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

5. 不同路径Ⅱ（LeetCode-63）

题目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

思路

五部曲

dp[m][n] 含义：到达m行n列有 dp[m][n] 条路径
机器人每次只能向下或向右移动，所以该点路径条数只与它上面和左边的点有关，是它们路径条数之和。这里比先前的题多了障碍，所以障碍这点的 dp 值为零
$\begin{cases} dp[m-1][n]+dp[m][n-1] & obstacleGrid[m][n]\neq1 \\ 0 & obstacleGrid[m][n]=1 \end{cases}$
初始化时，最左边一列和最上面一行的值肯定为1。但要注意如果有障碍，那么那点 dp 值要为零。还要注意只要有一个障碍，那它后面的值不用算了，肯定为零
要先有 $? 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));
        for (int i = 0; i < m; i++)
        {
            if (obstacleGrid[i][0] == 0)
            {
                dp[i][0] = 1;
            }
            else
            {
                dp[i][0] = 0;
                break;
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (obstacleGrid[0][i] == 0)
            {
                dp[0][i] = 1;
            }
            else
            {
                dp[0][i] = 0;
                break;
            }
        }
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (obstacleGrid[i][j] == 0)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
                else
                {
                    dp[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        return dp[m - 1][n - 1];
    }
};

6. 整数拆分（LeetCode-343）

题目

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

2 <= n <= 58

思路

拆数字 i ，可以得到的最大乘积为 dp[i]
可能会是两数相乘所得，也有可能是三数及以上相乘所得。这里就分两种情况取较大值即可。

变量 i 从 1 遍历到 n-1 ，两数相乘情况下结果为 $i ? (n ? i)$ ，三数及以上相乘情况下结果为 $i ? d p [n ? i]$ ???? 。这里的 dp[n-i] 是拆分数字 n-i 的最大乘积，其实是已经拆分过的，它就已经是几个数相加等于 n-i 的情况了，这点要理解，主要是想明白数组的含义
$d p [n] = m a x (i ? (n ? i), i ? d p [n ? i])$
dp[2]=1
先有 dp[n-i] 再有 dp[n] ，所以从前往后
测试用例

代码展示

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++)
            {
                // max函数只能两两比较
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

7. 不同的二叉搜索树（LeetCode-96）

题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

思路

这里用代码随想录的图分析一下

$n = 1$
$n = 2$
$n = 3$

可以分3种情况
1. 元素1为头结点时，没有比1小的元素了，所以左子树为空，右子树元素个数为二，就有 dp[2] 种组合。为什么是 dp[2] 种，题目不是说是由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种吗？这里呢其实大家要明白 dp[i] 的含义，也就是先定dp数组——i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种。我这里去掉了节点值从 1 到 n ，因为对于元素个数为2的二叉搜索树来说，无论它的元素值是 $1 ， 2$ 还是 $2 ， 3$ ，排列组合的结果都是一样的！
2. 元素2为头结点时，左子树元素个数为一，右子树元素个数也为一
3. 元素3为头结点时，左子树元素个数为二，右子树元素个数也为零
4. 所以 $d p [3] = d p [2] ? d p [0] + d p [1] ? d p [1] + d p [0] ? d p [2]$

五部曲

dp[i] 含义： i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种
变量 j 从 0 遍历至 i-1 ，dp[i] 初值为零
$d p [i] = d p [i] + d p [j] ? d p [i ? j ? 1]$
dp[0]=1 从定义上来讲，空节点也是?颗?叉树，也是?颗?叉搜索树
节点数为i的状态是依靠 i之前节点数的状态,所以从前往后
测试用例

代码展示

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 = 0; j < i; j++)
            {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
};

8. 小结

卡尔哥的方法是真的好用，写dp代码没多少，主要是五部曲写出思路。代码随想录yyds！

三、背包三讲

01背包

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

1. 例题（二维数组解法）

题目

背包最大重量为4

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问：背包能背的物品最大价值是多少？

思路

五部曲

数组含义
- 使用二维数组 dp[i][j]，含义：从下标为 $[0\sim i]$ 的物品中任意取，放入容量为 $j$ 的背包，价值总和最大为多少
递推公式由两个方向推出
- 一、不放物品 $i$ 的最大价值
  - 背包容量为 $j$ ，但不放物品 $i$ 时的最大价值，即 dp[i-1][j]
- 二、放物品 $i$ 的最大价值
  - 先找到 dp[i-1][j-weight[i]]，含义： $i ? 1$ 保证了不放物品 $i$ ，背包容量为 $j ? w e i g h t [i]$ 其实就是为了给后续放物品 $i$ 一个预留量，保证放了物品 $i$ 后背包不会溢出，所以最大价值为 dp[i-1][j-weight[i]]+value[i]
递推公式：
$d p [i] [j] = m a x (d p [i ? 1] [j], d p [i ? 1] [j ? w e i g h t [i]] + v a l u e [i])$
数组初始化
- 背包容量 $j$ 为零时，显然价值为零
- 只选物品0，即第一行，显然只要物品0重量小于等于背包重量 $j$ ，价值就为物品0的价值，否则为零
确定遍历顺序
- 先遍历背包还是物品都可以
- dp[i][j] 所需的数据在其左上方
测试用例

代码展示

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

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));
    for (int i = 1; i < bagWeight + 1; i++)
    {
        if (weight[0] <= i)
        {
            dp[0][i] = value[0];
        }
    }
    for (int j = 1; j < bagWeight + 1; j++)
    {
        for (int i = 1; i < weight.size(); i++)
        {
            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];
}

int main()
{
    test_2_wei_bag_problem1();
    return 0;
}

2. 例题（滚动数组解法）

还是之前的例子，可以用滚动数组将数组降为一维
$d p [i] [j] = m a x (d p [i ? 1] [j], d p [i ? 1] [j ? w e i g h t [i]] + v a l u e [i])$
由递推公式得： dp[i][j] 只和它的上一行有关，且有关元素的行数为 $i ? 1$ ，列数 $\le j$ 。那么我们就可以将数组压缩成一维


$d p [i ? 1] [j ? w e i g h t [i]]$		$d p [i ? 1] [j]$
		欲求元素

看这张表，如果数组是一维的情况，那么在算出欲求元素后，其实是将欲求元素覆盖掉 dp[i-1][j]，并且我们的遍历顺序也要改变。在二维情况下，我们是按从左到右的顺序求的，但在一维中，必须从右向左！因为在求欲求元素时，我们要保证 dp[i-1][j-weight[i]] 未被覆盖！同时，必须按照先遍历物品，再嵌套遍历背包的顺序。

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次

举例：

假设物品0重量 $w e i g h t [0] = 1$ ，价值 $v a l u e [0] = 15$

如果是正序遍历

$d p [1] = d p [1 ? w e i g h t [0]] + v a l u e [0] = 15$

$d p [2] = d p [2 ? w e i g h t [0]] + v a l u e [0] = 30$

在第一行运行后 $d p [1]$ 的状态已经发生改变，意味着已经放了物品0，而第二行运行后，叠加了改变后的 $d p [1]$ ，意味着物品0被放了两次。

那么为什么之前在写二维数组的时候是正序的？

因为我们实际求的是上一行的状态，也就是不放当前物品的情况，只不过在滚动数组中，压缩了状态。也即当前元素的公式被运行后，当前元素的状态（在当前行，包括物品0）覆盖了先前状态（在上一行，不含物品0），所以一维中倒序是为了保证物品只被放入一次！

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

void test_1_wei_bag_problem1()
{
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1);
    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];
}

int main()
{
    test_1_wei_bag_problem1();
    return 0;
}

3. 分割等和子集（LeetCode-416）

题目

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

思路

完全背包和01背包区别？

完全背包中一个商品可以放无数次
01背包中一个商品只能放一次

本题如何套？

分割成两个子集且元素和相等，即背包容量为 $s u m / 2$
物品重量为 $n u m s [i]$ ，价值也为 $n u m s [i]$
背包正好装满，就说明找到了 $s u m / 2$

五部曲

dp[i] 含义
- 背包容量为 $i$ 时，最大可以凑出的子集和
递推公式
- 本题中，物品重量为 $n u m s [i]$ ，价值也为 $n u m s [i]$
  $d p [j] = m a x (d p [j], d p [j ? n u m s [i]] + n u m s [i])$
数组初始化
- 都初始化为零
遍历顺序
- 先遍历物品，嵌套遍历背包，且背包遍历要倒序，不懂的回看例题
测试用例

代码展示

class Solution
{
public:
    bool canPartition(vector<int> &nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2)
        {
            return false;
        }
        int target = sum / 2;
        vector<int> dp(target + 1);
        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]);
                if (dp[target] == target)
                {
                    return true;
                }
            }
        }
        return false;
    }
};

对比卡尔哥的解法，用 target+1 做为数组大小，优化了空间。遍历中遇到一个吻合的直接返回 true，优化了时间。

4. 最后一块石头的重量Ⅱ（LeetCode-1049）

题目

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]
输出：5

示例 3：

输入：stones = [1,2]
输出：1

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 100

思路

如何套？

目的是求 最小的可能重量，其实也就是凑重量尽可能相等的两堆。举个例子 10，1，2，2，2，2，2 。我们就可以分为重量为 $11$ 和 $10$ 的两堆。

五部曲

dp[j] 含义
- 重量为 $j$ 的背包最大可以装的石头重量和
递推公式
- 本题中，物品重量为 $s t o n e s [i]$ ，价值也为 $s t o n e s [i]$
  $d p [j] = m a x (d p [j], d p [j ? s t o n e s [i]] + s t o n e s [i])$
数组初始化
- 设默认值零即可
遍历顺序
- 先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例

代码展示

class Solution
{
public:
    int lastStoneWeightII(vector<int> &stones)
    {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2;
        vector<int> dp(target + 1);
        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]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};

开始时没有考虑到问题是最小的可能重量。在 stones = [31,26,33,21,40] 这个样例中：一堆为 31，26，21 重量和为 $78$ ，另一堆为 33，40 重量和为 $73$ 。按照代码求法，target=75。求的是 dp[75]。为什么不是求 dp[73]？回看数组定义：重量为 $j$ 的背包最大可以装的石头重量和。可以看出：其实 dp[75] 与 dp[73] 是相等的

5. 目标和（LeetCode-494）

题目

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

思路

怎么套？

分成两堆， $l e f t ? r i g h t = t a r g e t$

又因为 $l e f t + r i g h t = s u m$

所以 $left=\cfrac{(sum+target)}{2}$

这和以前遇到的题目不一样

先前：容量为 i 的背包，最多能装多少？

这次：填满容量为 i 的背包，有多少种方法？

五部曲

数组定义
- dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法
递推公式
- 分两种情况，一种是不包含当前物品的方法数量，另一种是包含当前物品的方法数量。我们要求的就是二者之和。为了方便，直接使用一维数组展示：
  $d p [j] = d p [j] + d p [j ? n u m s [i]]$
数组初始化
- 如果是二维数组，也就是要初始化第一行，即只有物品零的情况，可以想见，填满背包容量为零的方法有一种，就是不装东西。但填满不为零的背包的方法却为零，除非物品重量等于背包容量。所以在一维数组中初始化应该是 dp[0]=1 其他为0
遍历顺序
- 先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例

代码展示

class Solution
{
public:
    int findTargetSumWays(vector<int> &nums, int target)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((sum < target) || ((sum + target) % 2) || ((sum + target) < 0))
        {
            return 0;
        }
        int left = (sum + target) / 2;
        vector<int> dp(left + 1);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = left; j >= nums[i]; j--)
            {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
};

6. 一和零（LeetCode-474）

题目

给你一个二进制字符串数组 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 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

思路

五部曲

dp[i][j] 含义
- 最多能装 i 个 $0$ 和 j 个 $1$ 的背包的最大子集的数量
递推公式
- 虽然是二维的，但其实只包含背包重量这一个方面，本质还是滚动数组。
  $d p [i] [j] = m a x (d p [i] [j], d p [i ? n u m Z e r o] [j ? n u m O n e] + 1)$
  其中， $n u m Z e r o$ 和 $n u m O n e$ 分别表示当前物品，即当前子集的零和一个数。相当于物品的重量。而后面的加一相当于物品的价值。为什么是一？因为加上当前物品后，最大子集数量就加一了。
数组初始化
- 物品价值不为负数，所以初始化为零即可
遍历顺序
- 先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例

本图为最后状态

代码展示

class Solution
{
public:
    int findMaxForm(vector<string> &strs, int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int idx = 0; idx < strs.size(); idx++)
        {
            int numZero = 0, numOne = 0;
            for (char val : strs[idx])
            {
                if (val == '0')
                {
                    numZero++;
                }
                else
                {
                    numOne++;
                }
            }
            for (int i = m; i >= numZero; i--)
            {
                for (int j = n; j >= numOne; j--)
                {
                    dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

完全背包

1. 例题

题目

有N件物品和一个最多能背重量为 $W$ 的背包。第 $i$ 件物品的重量是 $w e i g h t [i]$ ,得到的价值是 $v a l u e [i]$ 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。
在下面的讲解中，我依然举这个例子：
背包最大重量为4.
物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

每件商品都有无限个

问：背包能背的物品最大价值是多少？

思路

01背包和完全背包唯一不同在于遍历顺序上

01背包核心代码

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]);
 	}
}

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次

举例：

假设物品0重量 $w e i g h t [0] = 1$ ，价值 $v a l u e [0] = 15$

如果是正序遍历

$d p [1] = d p [1 ? w e i g h t [0]] + v a l u e [0] = 15$

$d p [2] = d p [2 ? w e i g h t [0]] + v a l u e [0] = 30$

在第一行运行后 $d p [1]$ 的状态已经发生改变，意味着已经放了物品0，而第二行运行后，叠加了改变后的 $d p [1]$ ，意味着物品0被放了两次。

那么为什么之前在写二维数组的时候是正序的？

因为我们实际求的是上一行的状态，也就是不放当前物品的情况，只不过在滚动数组中，压缩了状态。也即当前元素的公式被运行后，当前元素的状态（在当前行，包括物品0）覆盖了先前状态（在上一行，不含物品0），所以一维中倒序是为了保证物品只被放入一次！

而完全背包的物品是可以添加多次的，所以要从小到大去遍历

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

遍历顺序是否强制先遍历物品，再遍历背包容量？

在01背包的一维数组中必须先遍历物品，再遍历背包容量。

而在完全背包的一维数组中，循环嵌套顺序却无所谓。

因为 dp[j] 是根据它同行的左边的元素推出来的，而无论哪种顺序，它的左值都是更新过的，可用的。

但先后顺序可以颠倒的前提是纯完全背包问题！题目变化的可能就不行

代码展示

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

void test_CompletePack()
{
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1);
    for (int i = 0; i < weight.size(); i++)
    {
        for (int j = weight[i]; j <= bagWeight; j++)
        {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight];
}

int main()
{
    test_CompletePack();
    return 0;
}

2. 零钱兑换Ⅱ（LeetCode-518）

题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

提示：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000

思路

本题要点：

硬币有无限个，所以完全背包问题
本题要求凑成总金额的个数

五部曲

dp[j] 含义
- 凑成总金额为 $j$ 的硬币组合数（背包的容量为 $j$ 的背包恰好装满的方法数）
递推公式
- $d p [j] = d p [j] + d p [j ? c o i n s [i]]$
数组初始化
- dp[0]=1 从数组含义看：凑成总金额为零的硬币组合数为一
遍历顺序
- 先遍历物品，嵌套遍历背包，且背包遍历要正序
- 本题不是纯完全背包问题，不能交换顺序。因为本题求的是组合数，要求元素之间没有顺序。
测试用例

代码展示

class Solution
{
public:
    int change(int amount, vector<int> &coins)
    {
        vector<int> dp(amount + 1);
        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];
    }
};

3. 组合总和Ⅳ（LeetCode-377）

题目

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

思路

由示例一最后一行得，题目看似求的组合数，实际上求的是排序数

五部曲

dp[j] 含义
- 凑成目标正整数为 $j$ 的排列个数（使背包容量为 $j$ 的背包恰好装满的组合数——不同排序算做不同组合）
递推公式
- $d p [j] + = d p [j ? d p [n u m s]]$
数组初始化
- dp[0]=1
遍历顺序
- 先遍历背包，嵌套遍历物品，且物品遍历要正序
- 如果把遍历 nums（物品）放在外循环，遍历target的作为内循环的话，举?个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有 {3,1} 这样的集合，因为nums遍历放在外层，3只能出现在1后面

代码展示

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

4. 爬楼梯（改写成完全背包）

题目

原题为LeetCode-70，是一道简单动态规划，现改写为：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 $m$ 个台阶。你有多少种不同的方法可以爬到楼顶呢

思路

一步爬一个或两个或三个或 $m$ 个就是物品，楼顶就是背包，其实就是问装满背包的方法有多少种。再想这是排序数还是组合数？明显先2后1（先爬2阶楼梯再爬1阶楼梯）和先1后2是不同的方法，所以求的是排序数，那么就要求先遍历背包，嵌套遍历物品

五部曲

dp[j] 含义
- 爬到有 $j$ 个台阶的楼顶的方法数
递推公式
- $d p [j] + = d p [j ? i]$
数组初始化
- dp[0]=1
遍历顺序
- 上文已说明

代码实现

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

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

5. 零钱兑换（LeetCode-322）

题目

给你一个整数数组 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 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

思路

五部曲

dp[j] 含义
- 凑成总金额为 $j$ 所需的最少硬币数
递推公式
- 求最少硬币数，一种就是不含当前物品（这里说的当前物品就是指当前的这枚硬币，假如当前硬币值为2，不是说背包里就不含硬币值为2的硬币了，因为是硬币无限枚，所以很可能有，而是说不含当前这枚硬币值为2的硬币）的硬币数，数值保持不变。另一种是含当前物品的硬币数，数值要加一（加上当前物品）
  $d p [j] = m i n (d p [j], d p [j ? c o i n s [i]] + 1)$
数组初始化
- 凑成总金额为2的硬币数肯定为零，而其他要初始化为最大值，不然在运行递推公式时初始值会覆盖 $d p [j ? c o i n s [i]] + 1$
遍历顺序
- 这里求最少硬币数量，硬币是组合数还是排列数都无所谓，所以顺序随意

代码实现

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);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

易错点在 $d p [j ? c o i n s [i]]$ 是初始值没有跳过，还有记得没有任何一种硬币组合能组成总金额，返回 -1

6. 完全平方数（LeetCode-279）

题目

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

思路

看到示例一的 $4 + 4 + 4$ 知道是完全背包问题，本题求和为 n 的完全平方数的最少数量

五部曲

dp[j] 含义
- 和为 $j$ 的完全平方数的最少数量
递推公式
- 想一下，如果访问的当前物品是完全平方数，那么就分别求装它和不装它的数量，二者取小值。如果不是完全平方数，那么还是取不装它的数量
  $d p [j] = m i n (d p [j], d p [j ? i] + 1)$
数组初始化
- 和为 $0$ 的完全平方数的最少数量肯定为零，而其他要初始化为最大值
遍历顺序
- 这里求最少数量，是组合数还是排列数都无所谓，所以顺序随意

代码展示

class Solution
{
public:
    int numSquares(int n)
    {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            bool flag = false;
            if (i == 1)
            {
                flag = true;
            }
            for (int k = 0; k < i; k++)
            {
                if (k * k == i)
                {
                    flag = true;
                    break;
                }
            }
            for (int j = i; j <= n; j++)
            {
                if (flag && dp[j - i] != INT_MAX)
                {
                    dp[j] = min(dp[j], dp[j - i] + 1);
                }
            }
        }
        return dp[n];
    }
};

分析一下，很快写出来了。但时间复杂度过于之高。那肯定是求完全平方数没有处理好。看了下题解，是我的物品选错了，我是遍历数然后判断它是不是完全平方数，但这样做就烦了。数值 $n$ 什么时候完全平方数？说白了 $\sqrt{n}$ 是整数。那我的物品就取 $\sqrt{n}$

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

7. 单词拆分（LeetCode-139）

题目

给你一个字符串 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 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

思路

不会，卡尔哥的也没看懂。然后发现官方题解很清晰

我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串s[0~i?1] 是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i-1 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。公式化来说，我们需要枚举 s[0~i-1] 中的分割点 j ，看 s[0~j-1] 组成的字符串 $S_1$ （默认 j = 0 时 $S_1$ 为空串）和 s[j~i-1] 组成的字符串 $S_2$ 是否都合法，如果两个字符串均合法，那么按照定义 $S_1$ 和 $S_2$ 拼接成的字符串也同样合法。由于计算到 dp[i] 时我们已经计算出了 dp[0~i?1] 的值，因此字符串 $S_1$ 是否合法可以直接由 dp[j] 得知，剩下的我们只需要看 $S_2$ 是否合法即可，因此我们可以得出如下转移方程
$dp[i]=dp[j]\&\& check(s[j\sim i-1])$

五部曲

dp[i] 含义
- 表示字符串前 i 个字符组成的字符串s[0~i?1] 是否能被空格拆分成若干个字典中出现的单词
递推公式
- $dp[i]=dp[j]\&\& check(s[j\sim i-1])$
数组初始化
- dp[0]=true 表示字符串为空，但题目中说了“给定?个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为?个或多个在字典中出现的单词。
遍历顺序
- 实在是没看懂，直接复制卡尔哥的原话了

题?中说是拆分为?个或多个在字典中出现的单词，所以这是完全背包。
还要讨论两层for循环的前后循序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
本题最终要求的是是否都出现过，所以对出现单词集合?的元素是组合还是排列，并不在意！
那么本题使?求排列的?式，还是求组合的?式都可以。
即：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的。

但本题还有特殊性，因为是要求?串，最好是遍历背包放在外循环，将遍历物品放在内循环。如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的?串都预先放在?个容器?。（如果不理解的话，可以??尝试这么写?写就理解了）所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。

测试用例

代码展示

class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        unordered_set<string> wordset(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 0; i <= s.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end())
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

多重背包

LeetCode上无对应题目，只简单介绍

1. 多重背包例题

题目

有N种物品和一个容量为 $V$ 的背包。第i种物品最多有 $M_i$ 件可用，每件耗费的空间是 $C_i$ ，价值是 $W_i$ 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的，为什么和01背包像呢？

每件物品最多有 $M_i$ 件可用，把 $M_i$ 件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

	重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

问背包能背的物品最大价值是多少？

和如下情况有区别么？

	重量	价值	数量
物品0	1	15	1
物品0	1	15	1
物品1	3	20	1
物品1	3	20	1
物品1	3	20	1
物品2	4	30	1
物品2	4	30	1

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

思路

将有多件的物品展开，就可将完全背包转换成01背包

代码展示

#include <iostream>
#include <vector>
using namespace std;

void test_multi_pack()
{
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    for (int i = 0; i < nums.size(); i++)
    {
        while (nums[i] > 1)
        { // nums[i]保留到1，把其他物品都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }
    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]);
        }
        for (int j = 0; j <= bagWeight; j++)
        {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;
}
int main()
{
    test_multi_pack();
    return 0;
}

小结

做了这些题目后，感觉在没有系统学习dp之前，抓不住重点，有时稀里糊涂ac了，但不能完整推出来。所以说，卡尔哥的专题真的很有帮助！

四、打家劫舍

打家劫舍（LeetCode-198）

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 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 <= nums.length <= 100
0 <= nums[i] <= 400

思路

五部曲

dp[i]含义
- 偷窃前 i 个房子（包括房子i）可以获取的最大金额
递推公式
- $d p [i] = m a x (d p [i ? 1], d p [i ? 2] + n u m s [i])$
数组初始化
- dp[0]=0 dp[1]=nums[0]
遍历顺序
- 从前往后

代码

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

打家劫舍Ⅱ（LeetCode-213）

题目

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

思路

当房间数不超过二，不需要考虑首尾

超过二时，因为不能同时偷首尾房间，所以可以分两种情况考虑

不偷最后一间情况：盗窃范围 $n u m s [0 : n ? 2]$
不偷第一间情况：盗窃范围 $n u m s [1 : n ? 1]$

二者取较大值

代码展示

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }
        int left = robRange(nums, 0, n - 2);
        int right = robRange(nums, 1, n - 1);
        return max(left, right);
    }
    int robRange(vector<int> &nums, int start, int end)
    {
        if (start == end)
        {
            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 - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
};

打家劫舍Ⅲ（LeetCode-337）

题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104

思路

树形数组

确定递归函数参数与返回值
- 返回偷和不偷两种状态下获得的金钱。下标0表示不偷当前节点获得的最大金额，下标1表示偷当前节点获得的最大金额
确定终止条件
- 遇到空节点，肯定返回 ${0,0\}$
确定遍历顺序
- 必须后序遍历，因为要通过递归函数返回值后考虑
确定单层逻辑
- 如果偷当前节点
  - 左右孩子不能偷，即左右孩子各取下标0的值相加
    $v a l 1 = c u r . v a l + l e f t [0] + r i g h t [0]$
- 如果不偷当前节点
  - 左右孩子可以考虑偷，但到底偷不偷还是要判断
    $v a l 2 = m a x (l e f t [0], l e f t [1]) + m a x (r i g h t [0], r i g h t [1])$
测试用例

代码展示

class Solution
{
public:
    int rob(TreeNode *root)
    {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    vector<int> robTree(TreeNode *cur)
    {
        if (!cur)
        {
            return {0, 0};
        }
        vector<int> curleft = robTree(cur->left);
        vector<int> curright = robTree(cur->right);
        int val1 = cur->val + curleft[0] + curright[0];
        int val2 = max(curleft[0], curleft[1]) + max(curright[0], curright[1]);
        return {val2, val1};
    }
};

五、股票问题

买卖股票的最佳时机（LeetCode-121）

题目

给定一个数组 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 <= prices.length <= 105
0 <= prices[i] <= 104

思路

dp[i][取0或1] 的含义
- $d p [i] [0]$ 表示第 $i$ 天持有该股票所得现金
- $d p [i] [1]$ 表示第 $i$ 天不持有该股票所得现金
递推公式
- $d p [i] [0]$ 可由两个状态推出
  - 第 $i ? 1$ 天持有股票，则等于 $d p [i ? 1] [0]$
  - 第 $i$ 天买入股票，所得现金就为今天买入后 $? p r i c e [i]$
  - 选择所得现金最多的，即二者较大值
- $d p [i] [1]$ 可由两个状态推出
  - 第 $i ? 1$ 天不持有股票，则等于 $d p [i ? 1] [0]$
  - 第 $i$ 天卖出股票，则等于 $p r i c e [i] + d p [i ? 1] [0]$
  - 选择所得现金最多的，即二者较大值
数组初始化
- dp[0][0] 表示第0天持有股票，所以等于 $? p r i c e [0]$
- dp[0][1] 表示第0天不持有股票，等于0
遍历顺序
- 从前往后
测试用例

把用例自己脑子过一遍就懂了

代码展示

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        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], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
    }
};

滚动数组优化！

从递推公式可以看出，dp[i]只是依赖于dp[i - 1]的状态。

因此只要记录前一天和当天的状态就行

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

这优化法属实是把二进制玩明白了，我大为震撼。

买卖股票的最佳时机Ⅱ（LeetCode-122）

题目

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

思路

区别就在于可以多次买入！

唯一区别就在于递推公式的 $d p [i] [0]$

五部曲

dp[i][取0或1] 的含义
- $d p [i] [0]$ 表示第 $i$ 天持有该股票所得现金
- $d p [i] [1]$ 表示第 $i$ 天不持有该股票所得现金
递推公式
- $d p [i] [0]$ 可由两个状态推出
  - 第 $i ? 1$ 天持有股票，则等于 $d p [i ? 1] [0]$
  - 第 $i$ 天买入股票，由于可以多次买入，可能会出现之前已经买卖过一轮产生利润的情况，所得现金就为今天买入后 $d p [i ? 1] [1] ? p r i c e [i]$
  - 选择所得现金最多的，即二者较大值
- $d p [i] [1]$ 可由两个状态推出
  - 第 $i ? 1$ 天不持有股票，则等于 $d p [i ? 1] [1]$
  - 第 $i$ 天卖出股票，则等于 $p r i c e [i] + d p [i ? 1] [0]$
  - 选择所得现金最多的，即二者较大值
数组初始化
- dp[0][0] 表示第0天持有股票，所以等于 $? p r i c e [0]$
- dp[0][1] 表示第0天不持有股票，等于0
遍历顺序
- 从前往后

代码展示

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; 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]);
        }
        return dp[n - 1][1];
    }
};

买卖股票的最佳时机Ⅲ（LeetCode-123）

题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 105

思路

区别在于最多2次交易！

五部曲

dp[i][j] 的含义
- 一天一共有五种状态
- 0——没有操作
- 1——第一次买入
- 2——第一次卖出
- 3——第二次买入
- 4——第二次卖出
- $d p [i] [j]$ 表示在第 $i$ 天，状态 $j$ 下（j为上五种状态）所剩的最大现金
递推公式
- $d p [i] [1]$ 表示第一次买入股票的状态，并不是说一定在当天买入，可以之前买入，该天沿用。可由两个状态推出
  - 第 $i$ 天没有操作，沿用前一天状态，则等于 $d p [i ? 1] [1]$
  - 第 $i$ 天第一次买入股票，则等于 $d p [i ? 1] [0] ? p r i c e [i]$
  - 选择所得现金最多的，即二者较大值
- $d p [i] [2]$ 可由两个状态推出
  - 第 $i$ 天没有操作，沿用前一天状态，则等于 $d p [i ? 1] [2]$
  - 第 $i$ 天第一次卖出股票，则等于 $d p [i ? 1] [1] + p r i c e s [i]$
  - 选择所得现金最多的，即二者较大值
- $d p [i] [3]$ 可由两个状态推出
  - $d p [i] [3] = m a x (d p [i ? 1] [3], d p [i ? 1] [2] ? p r i c e s [i])$
- $d p [i] [4]$ 可由两个状态推出
  - $d p [i] [4] = m a x (d p [i ? 1] [4], d p [i ? 1] [3] + p r i c e s [i])$
数组初始化
- dp[0][0] 等于零
- dp[0][1] 等于 $? p r i c e [0]$
- dp[0][2] 虽然题目没有明确说是否允许同一天内买入并且卖出，但都不影响，因为这一操作收益始终为零
- dp[0][3] 等于 $? p r i c e [0]$
- dp[0][4] 等于零
遍历顺序
- 从前往后
测试用例

代码展示

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

这题比较复杂，但理清每个状态的含义就很清晰了

买卖股票的最佳时机Ⅳ（LeetCode-188）

题目

给定一个整数数组 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 。

提示：

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

思路

在做了买卖股票的最佳时机Ⅲ（LeetCode-123）后，肯定明白了除了状态0，其他的都是奇数买入，偶数卖出

五部曲就不写了，直接参考买卖股票的最佳时机Ⅲ（LeetCode-123）

代码展示

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

最佳买卖股票时机含冻结期（LeetCode-309）

题目

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

提示：

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

思路

五部曲

dp[i][j] 的含义
- 四种状态
  - 状态一：买入股票状态（今天买入股票或者之前买入就没有操作了）
  - 状态二：两天前就卖出了股票，度过了冷冻期
  - 状态三：今天卖出股票
  - 状态四：今天为冷冻期
递推公式
- $d p [i] [0]$ 可由两个状态推出
  - 第 $i ? 1$ 天持有股票，则等于 $d p [i ? 1] [0]$
  - 第 $i$ 天买入股票（今天买入），分两种情况
    - 前一天是冷冻期： $d p [i ? 1] [3] ? p r i c e s [i]$
    - 前一天是保持卖出股票状态： $d p [i ? 1] [1] ? p r i c e s [i]$
  - 选择所得现金最多的，即二者较大值
- $d p [i] [1]$ 可由两个状态推出
  - 第 $i ? 1$ 天就已经是状态二，则等于 $d p [i ? 1] [1]$
  - 前一天是冷冻期，则等于 $d p [i ? 1] [3]$
  - 选择所得现金最多的，即二者较大值
- $d p [i] [2]$ 只由一个状态推出
  - 前一天一定是买入股票的状态（状态一）： $d p [i ? 1] [0] + p r i c e s [i]$
- $d p [i] [3]$ 只由一个状态推出
  - 前一天一定是卖出股票的状态（状态三）： $d p [i ? 1] [2]$
数组初始化
- dp[0][0] 表示第0天买入股票，所以等于 $? p r i c e [0]$
遍历顺序
- 从前往后

代码展示

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(4));
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - 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][1], max(dp[n - 1][2], dp[n - 1][3]));
    }
};

这题挺绕的，不看题解完全不会写。

买卖股票的最佳时机含手续费（LeetCode-714）

题目

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104

思路

和 LeetCode-122 差不多类型，只要卖出时减去手续费就行

五部曲

dp[i][取0或1] 的含义
- $d p [i] [0]$ 表示第 $i$ 天持有该股票所得现金
- $d p [i] [1]$ 表示第 $i$ 天不持有该股票所得现金
递推公式
- $d p [i] [0]$ 可由两个状态推出
  - 第 $i ? 1$ 天持有股票，则等于 $d p [i ? 1] [0]$
  - 第 $i$ 天买入股票，由于可以多次买入，可能会出现之前已经买卖过一轮产生利润的情况，所得现金就为今天买入后 $d p [i ? 1] [1] ? p r i c e [i]$
  - 选择所得现金最多的，即二者较大值
- $d p [i] [1]$ 可由两个状态推出
  - 第 $i ? 1$ 天不持有股票，则等于 $d p [i ? 1] [1]$
  - 第 $i$ 天卖出股票，则等于 $p r i c e [i] + d p [i ? 1] [0] ? f e e$
  - 选择所得现金最多的，即二者较大值
数组初始化
- dp[0][0] 表示第0天持有股票，所以等于 $? p r i c e [0]$
- dp[0][1] 表示第0天不持有股票，等于0
遍历顺序
- 从前往后

代码展示

class Solution
{
public:
    int maxProfit(vector<int> &prices, int fee)
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; 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[n - 1][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

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

思路

五部曲

dp[i] 含义
- 包含下标 $i$ 的最长上升子序列
递推公式
- 寻找从 $0$ 到 $i ? 1$ 各个位置的最长上升子序列加一的最大值
- 在 $n u m s [i] > n u m s [j]$ 的情况下
  $d p [i] = m a x (d p [i], d p [j] + 1)$
数组初始化
- 每一个最长上升子序列起始长度至少为1
遍历顺序
- 从前往后
测试用例

代码展示

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

最长公共子序列（LeetCode-1143）

题目

给定两个字符串 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 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

思路

五部曲

dp[i][j] 含义
- 长度为 $[0, i ? 1]$ 的字符串text1与长度为 $[0, j ? 1]$ 的字符串text2的最长公共子序列长度
递推公式
- 如果 $t e x t 1 [i ? 1] = t e x t 2 [j ? 1]$ ?
  $d p [i] [j] = d p [i ? 1] [j ? 1] + 1$
- 如果二者不相等
  $d p [i] [j] = m a x (d p [i ? 1] [j], d p [i] [j ? 1])$
数组初始化
- dp[i][0] 与空串一起求最长公共子序列，自然为零
- dp[0][j] 同理等于零
遍历顺序
- 从前往后
测试用例

代码展示

class Solution
{
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        int n1 = text1.size();
        int n2 = text2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; 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[n1][n2];
    }
};

不相交的线（LeetCode-1035）

题目

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：

输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：

输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

提示：

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

思路

本质上和最长公共子序列（LeetCode-1143）一模一样。（公共子序列里的排序顺序不能改变）

代码展示

class Solution
{
public:
    int maxUncrossedLines(vector<int> &nums1, vector<int> &nums2)
    {
        int n1 = nums1.size();
        int n2 = nums2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; j++)
            {
                if (nums1[i - 1] == nums2[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[n1][n2];
    }
};

二、子序列（连续）

最长连续递增序列（LeetCode-674）

题目

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

提示：

1 <= nums.length <= 104
-109 <= nums[i] <= 109

思路

五部曲

dp[i] 含义
- 包含下标 $i$ 的最长连续递增序列
递推公式
- 判断下标 $i ? 1$ 是否是最长连续递增序列，如果是，加一
- 在 $n u m s [i] > n u m s [i ? 1]$ 的情况下
  $d p [i] = d p [i ? 1] + 1$
数组初始化
- 每一个最长上升子序列起始长度至少为1
遍历顺序
- 从前往后
测试用例

代码展示

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

比单纯的最长子序列还要简单

最长重复子数组（LeetCode-718）

题目

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

思路

和最长公共子序列（LeetCode-1143）的区别在于那题不要求连续，而本题是必须连续的子数组。

代码展示

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

最大子序和（LeetCode-53）

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路

五部曲

dp[i] 含义
- 包含下标 $i$ 的最大连续子数组和
递推公式
- 前面的最大和加上当前元素的值首先必须是正的才有积极意义，其次如果小于当前元素值，那么当前元素就没有必要带前面的一起，不如自己当头元素
  $d p [i] = m a x (d p [i ? 1] + n u m s [i], n u m s [i])$
数组初始化
- dp[0] 应该等于 $n u m s [0]$
遍历顺序
- 从前往后
测试用例

代码展示

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

三、编辑距离

判断子序列（LeetCode-392）

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

思路

和最长公共子序列（LeetCode-1143）类似

五部曲

dp[i][j] 含义
- 长度为 $[0, i ? 1]$ 的字符串s与长度为 $[0, j ? 1]$ 的字符串t的相同子序列长度
递推公式
- 如果 $s [i ? 1] = t [j ? 1]$ ?
  $d p [i] [j] = d p [i ? 1] [j ? 1] + 1$
- 如果二者不相等，沿用之前结果
  $d p [i] [j] = d p [i] [j ? 1]$
数组初始化
- dp[i][0] 与空串一起求最长公共子序列，自然为零
遍历顺序
- 从前往后
测试用例

代码展示

class Solution
{
public:
    bool isSubsequence(string s, string t)
    {
        int n1 = s.size();
        int n2 = t.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; 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[n1][n2] == n1 ? true : false);
    }
};

我直接修改最长公共子序列（LeetCode-1143）的代码做的结果，实际上就是看最长公共子序列长度是否为s字符串长度，如果相等，即s为t的子序列

class Solution
{
public:
    bool isSubsequence(string s, string t)
    {
        int n1 = s.size();
        int n2 = t.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; j++)
            {
                if (s[i - 1] == t[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[n1][n2] == n1 ? true : false);
    }
};

不同的子序列（LeetCode-115）

题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

示例 2：

提示：

0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

思路

五部曲

dp[i][j] 含义
- 以 $i ? 1$ 为结尾的字符串s子序列中出现以 $j ? 1$ 为结尾的字符串t的个数
递推公式
- 如果 $s [i ? 1] = t [j ? 1]$ ?
  - 一种方法是用 $s [i ? 1]$ 来匹配，个数为 $d p [i ? 1] [j ? 1]$
  - 即使相等，就一定要用它匹配？举个例子 $s : b a g g$ $t : b a g$ ， $s [3] = s [2]$ ，可以选着用 $s [3]$ 进行匹配，也可以不选，那就是用 $d p [i ? 1] [j]$
- 如果二者不相等，肯定不能用 $s [i ? 1]$ ，所以 $d p [i] [j] = d p [i ? 1] [j]$
数组初始化
- dp[i][0] 表示出现空字符串的个数，只有一种方法，就是全删，所以等于一
- dp[0][j] 表示空字符串出现以 $j ? 1$ 为结尾的字符串t的个数，只能为零
- dp[0][0] 空字符串可以删除0个元素，出现空字符串t，所以为一
遍历顺序
- 从前往后
测试用例

代码展示

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

两个字符串的删除操作（LeetCode-583）

题目

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

思路

五部曲

dp[i][j] 含义
- 以 $i ? 1$ 为结尾的字符串word1和以 $j ? 1$ 为结尾的字符串word2想要相等，需要删除元素的最小次数
递推公式
- 如果 $w o r d 1 [i ? 1] = w o r d 2 [j ? 1]$ ?
  - 次数为 $d p [i ? 1] [j ? 1]$
- 如果二者不相等，有下述三种情况
  - 删除 $w o r d 1 [i ? 1]$ ，最少操作次数为 $d p [i ? 1] [j] + 1$
  - 删除 $w o r d 2 [j ? 1]$ ，最少操作次数为 $d p [i] [j ? 1] + 1$
  - 二者取最小值
数组初始化
- dp[i][0] word2为空字符串，明显等于 $i$
- dp[0][j] word1为空字符串，明显等于 $j$
遍历顺序
- 从前往后
测试用例

代码展示

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n2; j++)
        {
            dp[0][j] = j;
        }
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; 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, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[n1][n2];
    }
};

编辑距离（LeetCode-72）

题目

给你两个单词 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')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

思路

五部曲

dp[i][j] 含义
- 将 $i ? 1$ 为结尾的字符串word1转换为 $j ? 1$ 为结尾的字符串word2，最少操作数为 $d p [i] [j]$
递推公式
- 如果 $w o r d 1 [i ? 1] = w o r d 2 [j ? 1]$ ?
  - 不进行任何操作，值为 $d p [i ? 1] [j ? 1]$
- 如果二者不相等，有下述三种情况
  - 首先要清楚word2添加一个元素，等价于word1删除一个元素！二者操作次数也均为一次！
  - 操作一：word1删除一个元素，最少操作次数为 $d p [i ? 1] [j] + 1$
  - 操作二：word2删除一个元素，最少操作次数为 $d p [i] [j ? 1] + 1$
  - 操作三：word1替换一个元素，最少操作次数为 $d p [i ? 1] [j ? 1] + 1$
  - 三者取最小值
数组初始化
- dp[i][0] 明显等于 $i$
- dp[0][j] 明显等于 $j$
遍历顺序
- 从前往后
测试用例

代码展示

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n2; j++)
        {
            dp[0][j] = j;
        }
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; 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, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1});
                }
            }
        }
        return dp[n1][n2];
    }
};

四、回文

回文子串（LeetCode-647）

题目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

思路

五部曲

dp[i][j] 含义
- 区间范围为 $[i, j]$ （注意左右都是闭区间）的子串是否为回文子串，元素类型为布尔类型
递推公式
- 当 $\neq s[j]$ 时，元素值必为 $f a l s e$
- 当 $s [i] = s [j]$ 时，分三种情况
  - 情况一： $i = j$ ，即二者下标相等，都指向同一个字符，肯定是回文子串
  - 情况二： $i$ 和 $j$ 下标相差 $1$ ，例如 $a a$ ，也是回文子串
  - 情况三：二者下标相差大于一，那必须看区间 $s [i + 1, j ? 1]$ 是不是回文子串
数组初始化

初始值全为 $f a l s e$

遍历顺序
- 要注意看当前元素依靠谁的状态获取，看到前文情况三，就知道肯定对于 $i$ 的遍历肯定要倒序。

代码展示

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

最长回文子序列（LeetCode-516）

题目

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

思路

五部曲

dp[i][j] 含义
- 在区间范围为 $[i, j]$ （注意左右都是闭区间）内的最长的回文子序列的长度
递推公式
- 当 $\neq s[j]$ 时，只说明二者不能同时加入回文子串，可以分别加入求最大值， $d p [i] [j] = m a x (d p [i + 1] [j], d p [i] [j ? 1])$
- 当 $s [i] = s [j]$ 时， $d p [i] [j] = d p [i + 1] [j ? 1] + 2$
数组初始化

当下标 $i = j$ 时，即一个字符的回文子序列长度应该为一

遍历顺序
- 要注意看当前元素依靠谁的状态获取，看到递推公式，就知道肯定对于 $i$ 的遍历肯定要倒序。

代码展示

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