【代码随想录】动态规划

动态规划基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的。贪心没有状态推导，而是从局部直接选最优的。

解题步骤：

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

如何debug：
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的

分治与递归、动态规划、贪心

分治法解决思路：

• 分解：将一个大问题分解成多个小问题（可以分解成两个问题或者多个问题
• 递归：递归解决每个小问题
• 合并：由子问题的解（小问题一定有边界条件）合并出大问题的解

比如斐波那契数列，假如要计算F(4)，可以将这个问题分解为
1.计算F(3)和F(2);
2.计算F(3)分解为计算F(2)和F(1);计算F(2)分解为计算F(1)和F(0);
3.得出子问题的解之后就可以组合出大问题的解。

动态规划解题思路：

基本性质：1.在分治法中会出现子问题重叠的现象。比如上面的例子中，会重复求F(2)与F(1)等。
2.最优子结构性质：原问题的最优解一定包含了子问题的最优解

基本步骤：
1、定义子问题，分析最优解的结构特征；
2、找出最优解对应的最优值，并递归地定义最优值；
3、以自底向上的方式计算出最优值；
4、根据计算最优值时得到的信息，构造最优解

比如求解斐波那契数列，求解F(n)，表示最优解，同时代表了最优值。那么F(n) = F(n - 1) + F(n - 2)。
于是就可以自底向上计算问题。f(1),f(2),f(3)…f(n)

动态规划与分治法比较：
1.对于子问题的划分：分治法常常对半分，动态规划是划分成n-1
2.求解过程：分治法采用递归，动态规划采用自底向上

斐波那契数

题目：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：
1、确定dp数组以及下标的含义：
dp[i]的定义是：第i个数的斐波那契数值是dp[i]
2、确定递推公式
状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
3、dp数组如何初始化

dp[0] = 0;
dp[1] = 1;

4、确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的。
5、举例推导dp数组按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

class Solution {
public:
    int fib(int n) {
        // 下面的代码要求至少2个元素
        if (n == 0) return 0;
        if (n == 1) return 1;

        // 定义dp数组和初始化
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 1;

        // 从左向右遍历
        for (int i = 2; i < n + 1; i++) 
            dp[i] = dp[i - 1] + dp[i - 2];

        return dp[n];
    }
};

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

实际上只需要维护两个数值就可以，不需要整个状态数组。所以空间复杂度为O(1)

思路2：采用递归的方式，从上到下计算

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

时间复杂度O(2^n)，空间复杂度O(n)，包括了实现递归所占用的系统栈的空间

递归的时间复杂度

面试题：求x的n次方

最直观：一个for循环

int function1(int x, int n) {
    int result = 1;  // 注意 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

时间复杂度是O(n)

一种递归：

int function2(int x, int n) {
    if (n == 0) {
        return 1; // return 1 同样是因为0次方是等于1的
    }
    return function2(x, n - 1) * x;
}

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。

每次n-1，递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1)，所以这份代码的时间复杂度是 n × 1 = O(n)。

另一种递归：

int function3(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;

    if (n % 2 == 1) {
        return function3(x, n / 2) * function3(x, n / 2)*x;
    }
    return function3(x, n / 2) * function3(x, n / 2);
}

我们来分析一下，首先看递归了多少次呢，可以把递归抽象出一棵满二叉树。刚刚同学写的这个算法，可以用一棵满二叉树来表示（为了方便表示，选择n为偶数16），如图：

当前这棵二叉树就是求x的n次方，n为16的情况，n为16的时候，进行了多少次乘法运算呢？

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以进行了多少次递归的话，就是看这棵树上有多少个节点。

这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示：(m为深度，从0开始)

时间复杂度忽略掉常数项-1之后，这个递归算法的时间复杂度依然是O(n)

最后一种递归：

int function4(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

再来看一下现在这份代码时间复杂度是多少呢？

依然还是看他递归了多少次，可以看到这里仅仅有一个递归调用，且每次都是n/2 ，所以这里我们一共调用了log以2为底n的对数次。

**每次递归了做都是一次乘法操作，这也是一个常数项的操作，那么这个递归算法的时间复杂度才是真正的O(logn)**。

爬楼梯

题目：70

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路1：每次可以选择爬1或者2个台阶

1.确定dp数组以及下标含义
dp[i]表示到达第i个阶梯的方法，

2.确定递推公式
dp[i] = dp[i - 1] + dp[i - 2]，表示登上第i-1层阶梯的方法之和再走一个阶梯，以及先登上第i- 2层阶梯的方法之和再走两个阶梯

3.初始化

由题意可知：dp[1] = 1；dp[2] = 2

4.遍历方式：后者必须依赖于前面两个元素，所以必须从前向后遍历

5.举例子

dp[1] = 1
dp[2] = 2
dp[3] = 3 = dp[1] + dp[2]
dp[4]: 1 1 1 1; 1 1 2; 1 2 1; 2 1 1; 2 2 一共5种，等于dp[3] + dp[2]

class Solution {
public:
    int climbStairs(int n) {
        // 下面的代码要求至少2个元素
        if (n == 0) exit(-1);
        if (n == 1) return 1;

        // 定义dp数组和初始化
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;

        // 从前向后遍历
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];

        return dp[n];
    }
};

思路2：采用分治或者说是递归的方式，同样由递推公式可得dp[i] = dp[i - 1] + dp[i - 2]，那么可以将一个大问题分解成小问题，递归解决小问题，小问题到达边界条件之后合并解决大问题。

时间复杂度O(2^n)：每计算一个F(n)都需要把这个结点分成两个结点，可以看作是一颗满二叉树，这个满二叉树的高度是n，于是可以得知一共有2^n级别个结点，这些结点都是一次递归操作，每次递归中的操作是O(1)级别的。

会超时。

使用最小花费爬楼梯

题目：746

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

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

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

思路：采用动态规划方式

1.dp数组即下标含义：
dp[i]表示到达第i层阶梯的最小花费

2.dp数组递推公式：
到达dp[i]有两种方式：（1）先到到达i-2，然后使用第i-2层的花费之后走两层到达第i层；（2）先到达第i-1层，然后使用第i-1层的花费之后走一层达到第i层。因此要使得dp[i]最小，就需要选择这两种方式中较小的一种。

另外需要注意的是，达到第i层不是终点，终点应该是走过所有楼梯，所以是第i+1层。

3.dp数组初始化：
可以从第0层或者第1层开始，所以到达这两层的最小花费是直接到达，即dp[0] = dp[1] = 0

4.遍历顺序：
因为i依赖于i-2和i-1，所以从前向后遍历

5.举例子尝试：
cost = [10,15,20]

(1)dp[0] = dp [1] = 0;

(2)dp[2]：选择有两种：第一种选择是：dp[0] + cost[0] = 10；第二种选择是：d[1] + cost[1] = 15；

(3)dp[3]：选择有两种：第一种选择是：dp[1] + csot[1] = 15；第二种选择是：dp[2] + cost[2] = 35;

所以最小花费是从下标1开始，走两层到达顶部（也就是第3层）

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 下面的代码要求至少有两个元素
        if (cost.size() == 0) exit(-1);
        if (cost.size() == 1) return 0;
        if (cost.size() == 2) return min(cost[0], cost[1]);
        
        // 定义dp数组和初始化
        // dp[i]表示到达第i层阶梯需要的最小花费
        vector<int> dp(cost.size() + 1, 0);
        dp[0] = dp[1] = 0;

        for (int i = 2; i <= cost.size(); i++) 
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

        return dp[cost.size()];
    }
};

时间复杂度O(n)，空间复杂度O(1)，这里只需要保留前两次数据即可。

阶段总结1

动态规划主要是用于解决这样的问题：1.存在子问题重叠；2.具有最优子结构，即原问题的最优解一定包含子问题的最优解

斐波那契数：递归公式就是动态数组的更新公式

爬楼梯：原问题定义为dp[i]到达第i层楼梯的方法数

使用最小花费爬楼梯：原问题定义为dp[i]到达第i层的最小花费数

注意这三道题后者只依赖于前两个元素，所以可以只保留前两个元素信息，使得空间复杂度降至O(1)

不同路径

题目：62

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

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

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

思路1：动态规划。怎么想出来的：尝试使用回溯的方法，到达一个点（i,j），剩余可以走的路径只有向右或者向下。发现子问题会存在重复，于是考虑到动态规划。想要到达（m,n），必须先到达（m-1,n）或者（m,n-1），因此可以将一个大问题划分成子问题。

1.dp数组以及下标含义：
这里dp数组是二维的，dp[i][j]表示到达（i,j）的路径数目

2.dp数组递推公式：
想要到达（i，j），要么（1）先到达（i-1，j）再向下移动一格；要么（2）先到达（i，j-1）再向右移动一格。于是可以得到
dp[i][j] = dp[i-1][j] + dp[i][j-1]

3.dp数组初始化：
第一行和第一列的元素都为1（dp[0][0]不应该存在，因为如果起点就是终点的话路径应该为0）

4.遍历顺序：
每一个元素依赖于上面的元素和左边的元素，所以按行从左向右遍历

5.举例子测试：假如m=3，n=2

首先初始化：第一行和第一列都是1，即dp(0,1) = 1, dp(1, 0) = 1, dp(2, 0) = 1

接着进行遍历（遍历从第二行的第二列开始）：dp(1, 1) = dp(0, 1) + dp(1, 0) = 2

接着遍历第三行：dp(2, 1) = dp(1, 1) + dp(2, 0) = 2 + 1 = 3

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 起点和终点相同时
        // 只有行或者只有列时
        if (m == 0 && n == 0) return 0;
        else if (m == 0) return 1;
        else if (n == 0) return 1;

        // 定义dp数组和初始化
        // dp[i][j] 表示到达(i, j)的方法数
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // 初始化第一行
        for (int c = 0; c < n; c++) 
            dp[0][c] = 1;
        // 初始化第一列
        for (int r = 0; r < m; r++)
            dp[r][0] = 1;

        // 从上到下、从左到右遍历
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++)
                dp[r][c] = dp[r-1][c] + dp[r][c-1];
        }

        return dp[m - 1][n - 1];
    }
};

时间复杂度O(m*n)，因为是遍历二维数组；空间复杂度O(m*n)，整个dp数组所占用的空间。是否可以优化？

优化：这里的遍历是从上到下，从左到右，并且每个元素只依赖于上边和左边元素。所以这里可以只使用一层也就是n个大小的数组来保存每一层的状态。每层更新时从左到右，上边的元素就是本身，左边的元素就是不断更新的元素。

时间复杂度降至O(n)

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 起点和终点相同时
        // 只有行或者只有列时
        if (m == 0 && n == 0) return 0;
        else if (m == 0) return 1;
        else if (n == 0) return 1;

        // 定义dp数组和初始化
        // dp[i][j] 表示到达(i, j)的方法数
        vector<int> dp(n, 0);
        // 初始化
        for (int c = 0; c < n; c++) 
            dp[c] = 1;
        
        // 从上到下、从左到右遍历
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++)
                dp[c] = dp[c] + dp[c-1];
        }

        return dp[n - 1];
    }
};

思路2：采用回溯的方式，每层回溯可以遍历的集合就是左和下。

使用一个全局遍历记录总的路径个数

递归的参数：终点(m,n)，当前位置(row,col)；没有返回值
递归的终止条件：当行或者列超出范围时，这时已经不是合理的范围；另外就是当前位置到达终点时也需要记录一个路径，并且返回
递归的单层逻辑：只能行增加或者列增加继续递归。

时间复杂度O(2^(m+n-1))，有递归树可以看出，每一个结点有两条孩子，是一颗满二叉树，这棵树的深度其实就是m+n-1（深度按从1开始计算）。空间复杂度就是时间复杂度，每一层都是一层递归栈。

class Solution {
public:
    int result;

    void BackTrace(int m, int n, int row, int col) {
        // 递归终止条件
        if (row == m-1 && col == n-1) {
            result++;
            return;
        }

        // 本层搜索逻辑
        // 向下递归
        if (row < m) BackTrace(m, n, row + 1, col);
        // 向右递归
        if (col < n) BackTrace(m, n, row, col + 1);
    }

    int uniquePaths(int m, int n) {
        // 范围检查：只有一个点或者只有一行或者只有一列
        if (m == 0 && n == 0) return 0;
        else if (m == 1) return 1;
        else if (n == 1) return 1;

        // 递归
        BackTrace(m, n, 0, 0);

        return result;
    }
};

会超时。

思路3：组合数学：从（1，1）到达（m，n），不管是什么走法（每一步只能向左或者向右），一定是向下走m-1步，向右走n-1步，一共是m+n-2步。

由于每次要么下要么右，并且必须有m-1个是向下，所以相当于在m+n-2次中有m-1个是向下操作（剩下的自然只能是向右）。

所以是组合数C

计算组合数的算法：

分子分母都是m个数相乘。不能先算出分子再算出分母，防止int类型溢出。所以采用边算边除以分母的方式：

// 使用组合数
   int uniquePaths(int m, int n) {
       long long numerator = 1; // 分子
       int denominator = m - 1; // 分母
       int count = m - 1;
       int t = m + n - 2; // 起点
       
       while (count--) {
           numerator *= (t--);
           // 当可以整除分母时
           // 由于是组合数，所以分子一定可以把所有的分母都给整除掉
           while (denominator != 0 && numerator % denominator == 0) {
               numerator /= denominator;
               denominator--;
           }

       }

       return numerator;
   }

时间复杂度O(m)

不同路径II*（待更新空间优化版本）

题目：63

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

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

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

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

思路1：采用深度优先搜索，每次可以选择搜索的集合就是右和下，如果是障碍物就不能搜索。

时间复杂度是O(2^(m +n -1))，感觉会超时

思路2：与上一题一样使用动态规划
1.dp数组以及下标含义：
dp[i][j]表示到达（i，j）可能的路径个数

2.dp数组递推公式：
遇上一题一样，想要到达（i，j），必须先到达（i-1，j）或者（i，j-1），所以
dp[i][j] = dp[i-1][j] + dp[i][j-1]
但是这里需要判断是否为障碍物。如果（i，j）是障碍物，那么这里的dp没有意义，就使用0表示；如果（i-1，j）或者（i，j-1）是障碍物，那么就不添加是障碍物的dp。如果都是障碍物，那么dp[i][j]就是0.

3.dp数组初始化：
（0，0）无意义，题目也说明不会只存在一个格子；
首先初始化第一行：（0，1）为1，然后依次向后初始化：如果第一行没有出现障碍物，那么全是1；如果出现障碍物，那么障碍物之后的都是0.
接着初始化第一列：（1，0）为1，然后依次向下初始化：如果第一列没有出现障碍物，那么全是1；如果出现障碍物，那么障碍物以下的都是0.

4.遍历顺序：
因此每一个元素都依赖于上面和左面，所以按行从左向右开始遍历

5.举例子：
示例1正确。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // 获取基本信息
        // 范围检查：
        int m = obstacleGrid.size();
        if (m == 0) return 0;
        int n = obstacleGrid[0].size();

        // 范围检查：如果只有一个格子
        if (m == 1 && n == 1 && obstacleGrid[0][0] == 0) return 1;

        // 错误检查：如果左上角为障碍则无意义
        if (obstacleGrid[0][0] == 1) return 0;
        // 如果右下角为障碍毫无意义
        if (obstacleGrid[m-1][n-1] == 1) return 0;

        // 定义dp数组
        // dp[i][j]表示到达(i, j)的方法数
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // 初始化行
        // 遇到石头后面的均为0，表示不可到达
        // 遇到石头之前的均为1，表示只有一条路径
        int c = 0;
        for (; c < n; c++){
            if (obstacleGrid[0][c] == 1) break;
            dp[0][c] = 1; 
        }
        // 将障碍物及障碍物后面置0
        while (c < n) dp[0][c++] = 0;

        // 同理处理列
        int r = 0;
        for (; r < m; r++) {
            if (obstacleGrid[r][0] == 1) break;
            dp[r][0] = 1;
        }
        while (r < m) dp[r++][0] = 0;

        // 从上到下、从左到右遍历
        for(r = 1; r < m; r++) {
            for (c = 1; c < n; c++) {
                // 如果当前位置是一个障碍物则为0
                if (obstacleGrid[r][c] == 1) dp[r][c] = 0;
                else dp[r][c] = dp[r-1][c] + dp[r][c-1];
            }
        }

        return dp[m-1][n-1];
    }
};

• 时间复杂度：O(n × m)，n、m 分别为obstacleGrid 长度和宽度
• 空间复杂度：O(n × m)

空间优化版本：待更新

整数拆分

题目：343

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

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

思路1：采用动态规划

1.dp数组以及下标定义：
dp[i]表示i被拆分之后最大乘积。

2.dp数组递推公式：
j从1到i-1开始遍历，得到dp[i]的方式有两种：（1）j * (i - j)；（2）j * dp[i - j]（相当于拆分 i - j）；通过比较这些值中最大的来确定dp[i]
因此递推公式为：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))
这里有dp[i]的原因是不断更新dp[i]的值，所以也参与到比较中

3.初始化：
i从2开始，每次j从1遍历到i / 2就可以，因为当 j 超过 i / 2之后，就开始重复

因为拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。

例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。

只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是 最差也应该是拆成两个相同的 可能是最大值。

那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。

至于 “拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的” 这个我就不去做数学证明了，感兴趣的同学，可以自己证明。

4.遍历顺序：
后者依赖于前者，所以从前向后遍历

class Solution {
public:
    int integerBreak(int n) {
        // 范围检查：n必须大于等于2

        // 定义dp数组
        vector<int> dp(n + 1, 0);
        // 初始化
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        // 从左向右遍历
        for (int i = 3; i <= n; i++) {
            // 将i值划分j 和 i-j
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], max(j * (i-j), j * dp[i-j]));
            }
        }

        return dp[n];
    }
};

时间复杂度O(n^2)，因为是双层循环；空间复杂度O(n)

不同的二叉搜索树

题目：96

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

示例1：

输入：n = 3
输出：5

思路1：动态规划

1.dp数组以及下标的含义：
dp[i]表示由i个结点组成互不相同的二叉搜索树的个数

2.dp数组递推公式：
j 从1遍历到 i ，表示以 j 值作为二叉搜索树的根节点。由于二叉搜索树根节点的左子树所有元素必须比根节点小，所以小于j的元素在左子树，大于j的元素在右子树。那么以结点 j 为根节点的二叉搜索树的个数就等于左子树种类数 与 右子树种类数的乘积。即dp[j] = dp[j - 1] * dp[i - j]。如果左子树节点数或者右子树节点数为0，那么应该为1，所以决定了dp[0]为1

所以只需要 j 从1遍历到n分别作为根节点求出dp[j] ，再把所有的dp[j]累加在一起就可以得到dp[i]

3.数组初始化：
上面可以得到，当j-1 == 0 或者i - j == 0即左子树或者右子树节点数为0时，为了方便与另一颗子树做乘法，所以dp[0] 应该为1；
另外dp[1] 为1.

4.遍历顺序：
dp数组第i个元素依赖于：从j-1到i-j（j取值为[1,i]），即依赖于dp[0]到dp[i - 1]，所以必须是从前向后遍历

5.举例子
n为3的例子正确

class Solution {
public:
    int numTrees(int n) {
        // 范围检查：n必须大0
        if (n == 0) exit(-1);

        // 定义dp数组
        // dp[i]表示i个不同值的节点能够构成的二叉搜索树数目
        vector<int> dp(n + 1, 0);
        // 初始化
        dp[0] = 1;
        dp[1] = 1;

        // 遍历节点数
        for (int i = 2; i <= n; i++) {
            // 以j值作为根节点
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        
        

        return dp[n];
    }
};

时间复杂度O(n^2）因为是双层循环；空间复杂度O(n)，因为第i个依赖于前i-1个，所以空间没办法优化。

动态规划总结

动态规划问题两个特征：（1）子问题会重叠；（2）原问题的最优解一定包含了子问题的最优解，这样才能由子问题状态一步步转移到原问题。

斐波那契数：（1）子问题会发生重叠：比如计算F(n)需要计算两个子问题F(n-1)和F(n-2)；这里面会发生问题重叠，因为计算F(n-1)同样需要计算F(n-2)和F(n-3)，于是F(n-2)发生重叠

（2）子问题的最优解就是方程得到的确定值，同时也是上一层问题的确定值。

状态转移方程就是dp[i] = dp[i - 1] + dp[i - 2]

爬楼梯：（1）子问题重叠：爬到n层楼梯的方法数目为F(n)，爬到n层楼梯需要先爬到n-1层再走一步，或者爬到n-2层再走2步；这里会发生重叠，因为爬到n-1层需要先爬到n-2层再走一步，或者先爬到n-3层再走2步。这里F(n-2)就会计算两次。

（2）分解成两个子问题的方法个数因为最后一步的不同而不同，求和即为原问题的解。

状态转移方程就是：dp[i] = dp[i - 1] + dp[i - 2]

使用最小花费爬楼梯：（1）子问题重叠：也是达到第n层需要先到达第n-1层或者n-2层，想要到达n-1层需要先到达n-2层或者n-3层。

（2）子问题的最优解包含在原问题的最优解：到达n-1层的最小花费，加上第n-1层花费；到达第n-2层的最小花费，加上第n-2层的花费。从这两者中选择一个小的作为第n层最小花费。

状态转移方程是：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

不同路径：（1）子问题重叠：想要到达[i, j] ，必须先到达[i - 1, j] 或者[i, j - 1]。而想要到达[i - 1, j]，需要先到达[i - 2, j] 或者[i - 1, j - 1]；同理，想要到达[i, j - 1] 需要到达[i - 1, j - 1] 或者[i, j - 2]，此时[i- 1, j - 1]重叠。

（2）子问题的最优解包含在原问题的最优解中：子问题到达[i - 1, j] 之后再向下走一格；子问题到达[i. j - 1]之后再想右走一格子。这两种到达[i, j] 的方式因为最后一步不同而不同，所以相加得到原问题的解。

状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

需要注意以下边界的初始化。

不同路径II：与上一题一样。不同的地方在于存在障碍物，如果是障碍物，那么dp[i][j]就为0，表示没有方法到达障碍物。

状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。如果后面的两个中有一个是障碍物，障碍物为0，不影响计算。

整数拆分：（1）子问题重叠：假设原问题的拆分之后的最大乘积是dp[i]，那么子问题为：(j 从1 ~ i-1)要么拆分成两个：j 和i - j；要么拆分成多个：j和dp[i - j] （即对i-j进行拆分的最大乘积，最少为2项）。在求dp[i - j ]时，需要求dp[i - 1]、dp[i - 2]等等，就会发生重叠。

（2）子问题的最优解推导出原问题的最优解：dp[i] 需要从：（1）j * (i - j)；（2）j * dp[i - j]（相当于拆分 i - j）；通过比较这些值中最大的来确定dp[i]

状态转移方程：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))

不同的二叉搜索树：

j 从1遍历到 i ，表示以 j 值作为二叉搜索树的根节点。由于二叉搜索树根节点的左子树所有元素必须比根节点小，所以小于j的元素在左子树，大于j的元素在右子树。那么以结点 j 为根节点的二叉搜索树的个数就等于左子树种类数 与 右子树种类数的乘积。即dp[j] = dp[j - 1] * dp[i - j]。如果左子树节点数或者右子树节点数为0，那么应该为1，所以决定了dp[0]为1

所以只需要 j 从1遍历到n分别作为根节点求出dp[j] ，再把所有的dp[j]累加在一起就可以得到dp[i]

（1）子问题重叠：比如求dp[2]，就必须求dp[0]、dp[1]；dp[1]、dp[0]；求dp[3]就会需要求dp[0]~dp[2]，所以存在子问题重叠

（2）最优解：原问题的最优解是通过子问题的最优解推导出来的。

01背包理论基础

问题描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

1.dp数组以及下标的含义：
对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2.确定递推公式：

再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

那么可以有两个方向推出来dp[i][j]，

1.不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
2.放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.初始化：
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
即第一列为0

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

4.遍历顺序：
更新时依赖于左上方的元素，因此可以按照行（即按照背包重量），也可以按照列（按照物品）

优化数组空间：在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把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]（一维数组，也可以理解是一个滚动数组）。

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

1.dp数组以及定义：
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2.递推公式：

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，

所以递归公式为：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3.数组初始化：
当j为0时，也就是数组第一个元素，应该为0.（因为容量为0的背包什么也不能装）
下标不为0应该如何初始化？dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

4.遍历顺序：代码如下：

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

    }
}

这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

（20240324注解：下面的说法太绕了，这样理解：这里每次内循环j开始重新遍历时，也就是重新开始一行，此时数组中的元素应该算作上一行的内容。那么假如j从小到大，那么j-weight[i]一定是从小到大，这样的遍历顺序会使得这一行数组前面覆盖掉后面的内容，从左向右更新，利用的是左边的值，所以会覆盖左边的值；如果j倒过来，j从大到小，j-weight[i]也从大到小，从右到左更新，利用的是右边的值，所以不会覆盖左边的值。）

为什么呢？

倒序遍历是为了保证物品i只被放入一次！一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

那么问题又来了，为什么二维dp数组历的时候不用倒序呢？

因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

（如何这里读不懂，大家就要动手试一试了，空想还是不靠谱的，实践出真知！）

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

不可以！

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

（这里如果读不懂，就再回想一下dp[j]的定义，或者就把两个for循环顺序颠倒一下试试！）

所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的！，这一点大家一定要注意。

分割等和子集

题目：416

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

思路：使得两个子集元素和相等，也就是使得其中一个子集的元素和为 sum/2

所以可以看成是背包的体积是 sum/2，并且如果背包正好装满，则说明找到了元素和为sum/2的子集

1.确定dp数组含义：
dp[j]表示容量为j的背包最大的权重

2.dp数组递推公式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);这里重量和价值都是元素的数值

3.初始化：
dp[0]为0，其它各元素也为0

4.遍历顺序：
外层循环是物品，内层循环从里向外遍历背包

5.测试

对于nums = [1,5,11,5]是可以的。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 范围检查：针对数组为空可以得出答案true

        // 计算总和
        int sum = 0;
        for (int x : nums) sum += x;

        // 其中一个子集和是总和的一半
        // 如果不能整除说明不可能
        if (sum % 2 == 1) return false;
        int target = sum / 2;
        
        // 定义dp数组和初始化
        vector<int> dp(target + 1, 0);

        // 外层循环遍历物品
        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;
        else return false;
    }
};

时间复杂度O(n^2)；空间复杂度O(n)

最后一块石头的重量II

题目：1049

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

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

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

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

思路：延续上一题的思路，这里以总重量的一半作为target，也就是目标背包的重量，转换为01背包问题，尽量装满这个背包，那么可以保证两个集合中石头重量的差值最小。

1.定义dp数组：
dp[j]表示容量为j的背包从所有种类的石头中选择，容量最大的重量。

2.递推公式：
dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])

3.初始化：
第一行表示没有物品，此时不管背包最大容量是多少，能够装的重量都是0

4.遍历顺序：
外层循环遍历物品，内存循环逆序遍历重量

5.测试用例

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        // 范围检查：空数组返回的答案是0

        // 计算总重量
        int sum = 0;
        for (int x : stones) sum += x;
        
        // 目标背包重量就是总重量的一半
        // 如果总重量是奇数那么一半重量就多个0.5
        // 而整数相加也不会加出个0.5
        // 也就是达不到target，所以不影响计算过程
        int target = sum / 2;

        // 定义dp数组和初始化
        vector<int> dp(target + 1, 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]);
        }

        // 背包承重为target的位置存放的就是最靠近一半重量的石头总和
        return sum - 2 * dp[target];
    }
};

时间复杂度O(m * n)，m是石头总重量的一半，n是数组长度；空间复杂度O(m)

目标和

题目：494

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

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

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

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

思路：

数组中所有数字都是非负的，计算总和为sum，假设选择其中一部分作为正数，其和为p，那么剩下的一部分就是作为负数，其和应该为-(sum - p)，这两部分的和应该等于target，也就是p=(sum+target) / 2。

要求运算结果等于target的表达式数目，也就是选中一些元素的和等于p的方法。

向下取整有没有影响？如果是奇数的话不可能有解；另外如果target的绝对值已经大于sum，说明所有元素同符号都不可能达到sum，也无解。

1.定义dp数组：
dp[j]表示从任意物品中选择，其值等于j的方法个数

2.递推公式：
假设第i间物品的重量是nums[i]，那么dp[j]等于所有dp[j - nums[i]]的累加，因为nums[i] + (j - nums[i]) 的重量刚好是j。
dp[j] += dp[j - nums[i]]

3.初始化：
dp[0]，一定要为1，因为如果第一个数字为0的话，后面的数字都将为0；
dp[j]，j不等于0时，应该初始化为0，保证可以正确进行累加。

4.遍历顺序：
外层循环遍历物品，内层循环逆序遍历重量

5.测试用例

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 范围检查：如果数组为空，并且target不能大于数组之和只能为0
        // 答案是1
        
        // 计算总和
        int sum = 0;
        for (int x : nums) sum += x;

        // 计算01背包重量
        if ((target + sum) % 2 == 1) return 0;
        if (abs(target) > sum) return 0;
        int p = (target + sum) / 2;

        // 定义dp数组和初始化
        // dp[i]表示装满最大承重为j的背包的方法个数
        vector<int> dp(p + 1, 0);
        dp[0] = 1;

        // 外层循环遍历物品
        for (int i = 0; i < nums.size(); i++) {
            // 内层循环逆序遍历重量
            for (int j = p; j >= nums[i]; j--)
                dp[j] += dp[j - nums[i]];
        }

        return dp[p];
    }
};

时间复杂度O(n^2)，空间复杂度O(大整数)

本题还是有点难度，大家也可以记住，在求装满背包有几种方法的情况下，递推公式一般为：

dp[j] += dp[j - weight[i]];

后面我们在讲解完全背包的时候，还会用到这个递推公式！

一和零

题目：474

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

思路：这里的思想是选中一个字符串添加到最终的子集中，这个子集的重量有两个维度，分别是0和1和个数。

1.定义dp数组：

dp[i][j]表示最多有i个0和j个1的背包中元素的个数

2.递推公式：
遍历每个字符串，假设当前字符串的0和1的个数为zero和one，要么放入该元素，此时背包中元素个数为：

dp[i - zeroNum][j - oneNum] + 1

要么不放入该元素，此时背包中的元素个数为：（与上一题作比较，相当于该上一个物品滚动下来的）

dp[i][j]

所以递推公式是：

dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

3.初始化：
初始时，所有背包中元素个数均为0

4.遍历顺序：
外层循环遍历物品，中层和内层循环逆序遍历重量

5.测试用例

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // 范围检查：如果m和n为0，返回0
        // 如果数组为空，返回0

        // 定义dp数组
        // dp[i][j]最多有i个0和j个1的背包中元素的个数
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        // 外层循环遍历物品
        for (const string &str : strs) {
            // 统计0和1的个数
            int zero = 0;
            int one = 0;
            // 下面的操作要求字符串只能由0和1字符构成
            for (const char &c : str) {
                if (c == '0') zero++;
                else one++;
            }

            // 内循环逆序遍历“重量”
            for (int i = m; i >= zero; i--) {
                for (int j = n; j >= one; j--)
                    dp[i][j] = max(dp[i][j], dp[i-zero][j-one] + 1);
            }
        }

        return dp[m][n];
    }
};

时间复杂度O(kmn)，k是字符串数量；空间复杂度O(mn)

完全背包理论

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

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背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次（这是因为外层循环是物品，内层循环是背包重量，如果是二维数组，那么每一层只会累计使用一次物品 i ）。

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

// 先遍历物品，再遍历背包
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] = max(dp[j], dp[j - weight[i]] + value[i]);

对于重量 j ，相当于内层循环遍历所有的物品，找到装入一个物品能够使得价值最高。

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的。因为重量不需要逆序，只要保证dp[j]能够根据之前的dp计算出来即可。

零钱兑换II

题目：518

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

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

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

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

思路：典型的完全背包问题

1.定义dp数组以及下标
dp[j]表示将容量为 j 的完全背包装满的方法数

2.确定递推公式
dp[j] += dp[j - weight[i]]，后者表示容量为 j - weight[i]的背包装满的方法，现在又装进一个物品 i，将所有的容量能够新装如一个物品 i 的方法相加即可得到。

3.初始化：
dp[0]表示将背包容量为0，那么应该只有一种方法，就是什么都不装。如果dp[0]为0的话，后面累加均为0。比如dp[1]最多只能装下一个重量为1的元素，所以等于dp[0]；而dp[2]可以装下重量为1或者2的元素，所以是dp[0] + dp[1]。

4.确定遍历顺序：
外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况，此时是组合数。
如果把两个for交换顺序，此时dp[j]里算出来的就是排列数。
（外层是物品时，使用完i - 1号物品之后，以后都不会再尝试使用1号物品；内层是物品时，对于背包0 ~ target，每次都会尝试使用所有物品，也就是会出现前面的结果是{1，5}，后面一次的结果可能是{5，1}）

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 范围检查：如果amount为0，返回结果1，表示哪一种硬币都不选
        // 如果硬币为空，返回结果为0
        
        // 定义dp数组和初始化
        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];
    }
};

时间复杂度O(mn)，m是重量，n是物品数量；空间复杂度O(m)

动态规划总结（01背包和完全背包，组合和排列）

主要介绍了两种背包，第一种是01背包，即存在 i 种物品，重量是weight[i]，价值是value[i]。背包的能够承受的最大重量是MaxWeight，每个物品只有1个，如何选择物品使得总价值最大。第二种是完全背包，区别在于物品的个数是无限个。

对于01背包的问题分类：
1.使得价值最高：这一类问题往往需要进行转换，搞清楚背包的重量是什么。比如分割等和子集、最后一块石头的重量II，背包的重量可以看作是总和的一半。
2.求满足背包重量的组合数（方法数）：这里是求刚好把背包装满的方法。关键的递推公式是：dp[j] += dp[j - weight[i]];

对于完全背包的问题分类：
1.使得价值最高：与01背包不同的是遍历顺序，01背包要求外层循环必须是物品数，内层循环是重量且必须是逆序（从二维数组考虑，右下角元素依赖于左上角元素，如果从左向右遍历，那么左边元素依次被覆盖；另外如果物品在内循环，外循环必须是重量逆序，会使得每种背包只放一个元素）。而完全背包对于内外层循环没有要求，且不能逆序。
2.求满足背包的组合数和排列数：求组合数就是让物品在外层循环，求排列数就是让重量在外层循环。（这样考虑，物品在外层循环时，内层更新所有的重量，轮到下一个物品时不会再装上一个物品；物品在内层循环时，对于每一种重量，都会使用所有的物品放进去尝试。）比如零钱兑换II种求的是方法个数，也就是组合数，所以物品必须在外层遍历。

组合总和IV

题目：377

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

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

思路：和上面讨论的一样，对于完全背包的排列数问题。外层循环是重量，内层循环是物品。

这里需要注意的是，题目保证答案是32位无符号整数。

1.定义dp数组：
dp[j]表示总和是j的元素组合的个数

2.递推公式：
dp[j]等于所有j - nums[i]的背包的方法总和，表示重量为j - nums[i]中的排列个数再加上第i个元素之后排列个数。

dp[j] += dp[j-nums[i]]

3.初始化：
dp[0]表示总和为0的排列方法，只能是“什么都不选”这1种排列方法。另外如果dp[0]为0，那么后面所有的元素都为0.

4.遍历顺序：
外层遍历重量，内层遍历价值，这样才是排列数

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // 范围检查：如果target为0，返回1，表示只有“什么都不放”这一个方法
        // 如果数组为空，返回0
        
        // 定义dp数组
        // dp[i]表示总和为i的元素的组合个数
        vector<unsigned int> dp(target + 1, 0);
        // 初始化
        // 目标值为0，表示只有“什么都不放”这一种选择
        // 如果dp[0]为0，后面的元素都为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] += dp[j-nums[i]];
            }
        } 

        return dp[target];
    }
};

时间复杂度O(target * n)；空间复杂度O(target)

爬楼梯（进阶版）

题目：70（基础版）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路 ：将其看作是一个完全背包问题，物品只有两个，就是1和2，背包重量是n，求刚好组成n的排列数。

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

class Solution {
public:
    int climbStairs(int n) {
        // 范围检查：如果n为0，答案是1，表示“不动”这一种方法

        // 定义dp数组
        // dp[i]表示背包承重为n的排列数
        vector<int> dp(n + 1, 0);
        // 初始化，承重为0只有“什么都不选”这一种方法
        // 如果初始值为0，那么根据递推公式后面都为0
        dp[0] = 1;

        // 外层循环遍历重量
        // 才是排列数
        for (int j = 0; j <= n; j++) {
            // 内层循环遍历物品
            for (int i = 1; i <= 2; i++) {
                if (j - i >= 0) dp[j] += dp[j - i];
            }
        }

        return dp[n];
    }
};

之前采取dp[i] = dp[i - 1] + dp[i - 2]的时间复杂度是O(n)，空间复杂度是O(1)

以及采取分治法，也就是递归的方法，时间复杂度是O(2^n)，因为将每个问题分成两个子问题，知道问题的规模是1或者2，所以可以看作是一个二叉树，每个结点的时间复杂度是O(n)，大致2^n个结点。

进阶版：每次可以走1~m个阶梯，其实就是可选择物品为m个，内层循环遍历m个物品即可。

零钱兑换

题目：322

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

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路：每种物品的数量无限，所以是一个完全背包问题。

1.定义dp数组和下标定义
dp[j]表示重量为 j 的背包装满后最小的物品个数。

2.确定递推公式：
dp[j] = min（dp[j]，dp[j - amount[i]] + 1）。表示重量为j - amount[i]的背包加上目前物品的重量，刚好是重量j的背包，但是多加了一个物品个数。

3.初始化：
dp[0]表示重量为0的背包需要的硬币个数为0；对于其它重量来说，应该初始化为一个比较大的数字。

4.遍历顺序：
本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 范围检查：如果amount为0，答案是0
        // 如果数组为空，返回-1

        // 定义dp数组
        vector<int> dp(amount + 1, INT_MAX);
        // 初始化
        dp[0] = 0;

        // 外层循环遍历重量
        for (int j = 0; j <= amount; j++) {
            // 内层循环遍历物品
            for (int i = 0; i < coins.size(); i++) {
                if (j >= coins[i] && dp[j-coins[i]] != INT_MAX) 
                    dp[j] = min(dp[j], dp[j-coins[i]] + 1);
            }
        }

        if (dp[amount] == INT_MAX) return -1;
        else return dp[amount];
    }
};

时间复杂度O(amount * n)；空间复杂度O(amount)

完全平方数

题目：279

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

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

思路：物品是小于等于n的完全平方数，背包重量是n，求装满背包的最小的物品数量。

与上一题一致。

class Solution {
public:
    int numSquares(int n) {
        // 范围检查：如果n为0，答案是0

        // 定义dp数组
        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++) {
                if (dp[j - i*i] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - i*i] + 1);
            }
        }

        return dp[n];
    }
};

时间复杂度O(n ^ (3/2))，空间复杂度O(n)

总结

主要有两种类型：

完全背包（即物品数为无限个）：
1.组合与排列数：如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。这里是求组合数或者排列数，递推公式为：dp += dp[j - amount[i]] + 1；
2.求装满背包使用最少的物品个数：递推公式为dp[j] = min（dp[j]，dp[j - amount[i]] + 1）

单词拆分

题目：139

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路1（动态规划）：背包就是字符串s，物品就是单词，能否组成字符串，就是物品能否将背包装满。

1.定义dp数组和下标
dp[i] 表示字符串长度为 i 时能否由字典中的单词构成

2.确定递推公式：
如果dp[i] 是true，那么如果[i + 1, j]这个长度区间中的子串 出现在字典中，那么dp[j] 一定是true

更新的时候应该是从前向后更新dp数组，所以想要更新dp[j] ，必须确定dp[i] ，也就是字符数量少于 j 的背包。

3.初始化：
dp[0]表示长度为0的字符串，一定可以由字典组成，所以是true

4.遍历顺序：
因为求的是物品的排列形式，所以背包在外面，物品在内循环

bool wordBreak(string s, vector<string>& wordDict) {
    // 使用无序集合方便在其中查找单词
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());

    // 定义dp数组和初始化
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;

    // 外层循环遍历背包
    // i表示背包长度
    for (int i = 1; i <= s.size(); i++) {
        // 内层循环遍历背包后面的物品
        // s[0, j)表示背包中的字符串
        // s[j, i)表示背包后面的字串
        for (int j = 0; j < i; j++) {
            string back = s.substr(j, i - j);
            if (wordSet.find(back) != wordSet.end() &&
                dp[j] == true) {
                dp[i] = true;
            } 
        } // end of for j in range[0, i)

    } // end of for i in range[1, s.size()]

    return dp[s.size()];
}

时间复杂度O(n^3)，包括两层循环以及在返回字串的副本的复杂度O(n）；空间复杂度O(n)

思路2：回溯法：类似于回文串切割：

只有当前面切割的字符串能够在单词表中查找到时，才进行递归切割。

1.递归的参数以及返回值：
参数包括总的字符串、起点、以及单词表，返回值表示能否切割

2.递归终止条件
当起点到达字符串长度时，说明前面都已匹配成功。

3.单层处理逻辑：
从起点开始向后遍历组成字符串，即s[start_index, i]，如果这一段字串能够在单词表找到，并且以i + 1为起点进行递归，如果也返回true，说明可以由单词表构成，所以返回true。回溯的过程就是没有递归没有返回true时，i 仍然是旧值，新的子串是从s[start_index, i]到s[start_index, i + 1]

bool BackTrace(const string &s, const int start_index, const unordered_set<string> &word_set) {
    // 递归终止条件
    if (start_index >= s.size()) return true;

    // 单层处理逻辑
    for (int i = start_index; i < s.size(); ++i) {
        string str = s.substr(start_index, i - start_index + 1);
        if (word_set.find(str) != word_set.end() && BackTrace(s, i + 1, word_set))
            return true;
    }

    return false;
}


bool wordBreak(string s, vector<string>& wordDict) {
    // 使用无序集合方便在其中查找单词
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());

    // 回溯
    return BackTrace(s, 0, wordSet);

}

会超时，时间复杂度O(2^n)

多重背包理论

多种背包与01背包和完全背包的区别就是：多种背包中物品 i 的数量是Mi。

解决方法就是将Mi个 物品 i 作为Mi个相同的物品 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背包问题了，且每个物品只用一次。

背包问题总结

整体步骤：

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

递推公式：
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
问装满背包有几种方法：dp[j] += dp[j - nums[i]]
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])

遍历顺序：
01背包：二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历

完全背包：纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品

打家劫舍

题目：198

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

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

思路：由于每家最多偷盗一次，所以这是一个01背包问题。在不受限制的情况下可以将所有目标均偷盗，所以背包重量最大为个数。

每个物品的价值就是每一家的金额数。

1.定义dp数组和下标
dp[i] 表示偷盗前 i 家时最大的金额，其中 i 表示物品下标

2.递推公式：
想要确定dp[i]，有两种方式：第一种是选择第 i 家，就不能选择第i - 1家，那么此时金额为 dp[i - 2] + nums[i]；第二种方式是不选择第 i 家，因为不偷第 i 家，所以此时金额就是dp[i - 1]

3.dp数组初始化
dp[0] = nums[0]

dp[1] = max(nums[0], nusm[1])

4.确定遍历顺序：
由于依赖于前面的数据，因此只能从前向后

class Solution {
public:
    int rob(vector<int>& nums) {
        // 范围检查：下面的操作要求至少2个元素
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];

        // 定义dp数组
        // dp[i]表示偷到i个房子能偷盗的最大金额
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0]; // 0个房子偷盗最大金额为nums[0]
        dp[1] = max(nums[0], nums[1]);

        // 遍历每个房子
        for (int i = 2; i < nums.size(); i++) {
            // 有两种选择：
            // 要么偷第i家，那么第i-1家就不能偷
            // 要么不偷第i家，那么金额与上次一样
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }

        return dp[nums.size()-1];
    }
};

时间复杂度O(n)；空间复杂度O(n)，实际上可以优化为只保存为前两个数据，不需要整个dp数组。

class Solution {
public:
    int rob(vector<int>& nums) {
        // 范围检查：下面的操作要求至少2个元素
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];

        // 定义dp数组
        // dp[i]表示偷到i个房子能偷盗的最大金额
        int pre_pre = nums[0]; // 0个房子偷盗最大金额为nums[0]
        int pre = max(nums[0], nums[1]);

        int result = pre;
        // 遍历每个房子
        for (int i = 2; i < nums.size(); i++) {
            // 有两种选择：
            // 要么偷第i家，那么第i-1家就不能偷
            // 要么不偷第i家，那么金额与上次一样
            result = max(pre, pre_pre + nums[i]);

            // 更新
            pre_pre = pre;
            pre = result;
        }

        return result;
    }
};

打家劫舍II

题目：213

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

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

思路：由于是循环的数组，第一个和最后一个相邻，不能同时选择

所以关键在于二者的状态：

第一种：二者都不在选择中，即从第二个到倒数第二个，这样二者都不会选

第二种：第一个不在选择中，即从第二个到最后一个，这样可以选最后一个（即选择最后一个，不选择第一个），也可以不选最后一个（这种情况下就是二者都不选，与第一种情况相同）

第三种：最后一个不在选择中，即从第一个到倒数第二个（选择第一个，不选择最后一个），这样可以选第一个，也可以不选第一个（同情况一）

上述第二种和第一种就已经包含了二者的三种状态。

dp数组与上一题一致，不同的是物品的范围。

class Solution {
public:
    int rob(vector<int>& nums) {
        // 范围检查：下面的操作要求至少2个元素
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];

        // 定义dp数组和初始化
        vector<int> dp(nums.size(), 0);
        // 偷第一家，不能偷最后一家
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        // 注意下标，不偷最后一家
        for (int i = 2; i < nums.size()-1; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        int result1 = dp[nums.size() - 2];

        // 不偷第一家，可以偷最后一家，也可以不偷最后一家
        dp.clear();
        dp[0] = 0;
        dp[1] = nums[1];
        // 注意下标，不偷第一家
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        int result2 = dp[nums.size()-1];

        return max(result1, result2);        
    }
};

时间复杂度O(n)，相当于做两次n；空间复杂度O(n)，dp数组消耗空间

打家劫舍III

题目：337

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

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

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

思路1：

1.定义dp数组和下标含义
dp(cur)：表示以cur为根节点的树的最大值，这个最大值有两种可能，（1）不选cur，那么就需要知道左孩子和右孩子的最大值；（2）选则cur，那就不能选择左孩子和右孩子，只能选择左子树且去除左孩子的最大值，和右子树且取出右孩子的最大值

因此返回值是一个vector，这样就能保存{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}，进而计算出根结点的最大值

2.递推公式如1所述

3.初始化：
即对于空结点或者没有孩子的结点的树来说。
首先是空结点，那么：（1）不偷当前结点的最大值：0；（2）偷当前结点的最大值为0
其次是没有左孩子和右孩子的结点，那么（1）不偷当前结点的最大值：0；（2）偷当前结点的最大值，当前结点的值
然后是只有一个孩子的结点，那么（1）不偷当前结点的最大值：这个孩子的值；（2）偷当前结点的最大值，max(当前结点的值, 孩子的值)
最后有两个孩子的结点，那么（1）不偷当前结点的最大值：左子树最大值+右子树最大值；（2）偷当前结点的最大值：当前结点的值+不偷左子树的根节点的最大值+不偷右子树的根节点的最大值

上面几种情况存在重叠，其中第2、3与第4种情况重叠

4.遍历顺序：
采用后序遍历，先计算左右子树的返回值，再由此计算当前的返回值

5.单层逻辑如3所述

时间复杂度O(n)，相当于遍历一遍二叉树的所有节点；空间复杂度O(logn)，系统递归调用栈

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // vector[0]表示不偷当前节点的最大值，
    // vector[1]表示偷当前节点的最大值
    vector<int> PostTraversal(TreeNode *cur) {
        vector<int> result{0, 0};

        // 空结点进入递归
        if (cur == nullptr) return result;

        // 首先递归左右孩子
        vector<int> left = PostTraversal(cur->left);
        vector<int> right = PostTraversal(cur->right);
        
        // 不偷当前节点的最大值
        result[0] = max(left[0], left[1]) + max(right[0], right[1]);
        // 偷当前节点的最大值
        result[1] = cur->val + left[0] + right[0];

        return result; 
    }

    int rob(TreeNode* root) {
        // 空结点可以进入递归
        vector<int> result = PostTraversal(root);

        return max(result[0], result[1]);
    }
};

思路2：

暴力递归：

int rob(TreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return root->val;
    // 偷父节点
    int val1 = root->val;
    if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left，相当于不考虑左孩子了
    if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right，相当于不考虑右孩子了
    // 不偷父节点
    int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
    return max(val1, val2);
}

对于每一个结点来说，都需要计算一遍以这个结点为根的子树的所有结点的最大值，这里面一定会存在大量的子问题重叠，并且父节点的最优解是由孩子结点和孙子结点两个子问题的最优解计算出来（原问题的最优解包含子问题的最优解）。解决方法就是需要保存一下曾经计算过的子问题的解，作者这里给出了一种使用map保存中间结果的方法。

与上面使用动态规划的方法其实本质上是一样的，动态规划本身就是自底向上计算，这样就能利用前者计算后者的解。
而传统的二叉树必然是自顶向下遍历，所以采用后序遍历实现自底向上访问所有结点，这样能把子问题的解作为结果传递给更大的问题。

unordered_map<TreeNode* , int> umap; // 记录计算过的结果

总结

打家劫舍：这里的限制是对于一个数组来说，不能偷相邻的两家，所以使得递推公式中，要么偷第 i 家，不能偷第i - 1家；要么偷第 i - 1家，不偷第 i 家。选择价值更大的。

打家劫舍II：数组成环，所以需要考虑最后一个和第一个的关系，即只能从都不考虑、考虑起点不考虑终点、不考虑起点考虑终点中选择最大的一个

打家劫舍III：对于二叉树的动态规划，这里动态规划的思想是自底向上，所以采用后序遍历；因为二叉树的遍历涉及到递归，且不能提前知道有多少个节点，所以只能将后者依赖的值作为递归函数的返回值传递。（这里貌似也可以使用后序遍历的非递归形式，只不过由于不能提前知道节点数，所以dp数组的大小不能提前确定）

买卖股票的最佳时机

题目：121

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路1：采用暴力解法：双层循环，外层循环是表示某一天买入，内层循环尝试后面的一天卖出，计算最大的差值就是利润。

时间复杂度O(n^2)；空间复杂度O(1)

class Solution {
public:
    // 暴力法
    int maxProfit(vector<int>& prices) {
        // 范围检查：如果数组为空返回0
        // 如果数组只有1个元素返回0

        int prices_size = prices.size();
        int max_profit = 0;

        // 外层循环遍历每一天作为购买日
        for (int i = 0; i < prices_size; i++) {
            // 内层循环遍历剩余天作为卖出日
            for (int j = i + 1; j < prices_size; j++) {
                max_profit = max(max_profit, prices[j] - prices[i]);
            }
        }
        
        return max_profit;
    }
};

会超时。

思路2：贪心算法：取局部状态下（比如当前只有n个数字，第n + 1个数字比前n个数字中最小值都要小），最左边的最小值和最右边的最大值（就是前n个数字中的最左最小值和最右最大值）。
整体最大值：从所有局部状态下选取最大的值。

从左向右遍历，维护一个最小值；维护一个结果值，只有当price[i] - 最小值比结果值大时才更新。

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

class Solution {
public:
    // 贪心法
    int maxProfit(vector<int>& prices) {
        // 范围检查：数组长度为0和1返回0

        int min_num = INT_MAX;
        int max_profit = 0;
        
        // 从前向后遍历
        for (int i = 0; i < prices.size(); i++) {
            // 更新最小值
            min_num = min(min_num, prices[i]);
            // 更新结果
            max_profit = max(max_profit, prices[i] - min_num);
        }

        return max_profit;
    }
};

思路3：动态规划

1.定义dp数组和下标：
dp[i][0]表示第 i 天持有股票所得最多现金，假如前一天没有持有股票，但是今天持有股票，说明今天购入股票，此时现金为:
-prices[i]
dp[i][1]表示第 i 天不持有股票所得最大现金。
（我的思路：定义dp[i]为第 i 天所得最多现金，由于只能购买和卖出一次，这里的问题就是不知道哪一天购入的股票，因此也就无法得知哪一天卖出能够或得最大利润。作者记录之前一天的两种状态，有和没有股票，这样就能判断是哪一天买入，从而计算哪一天卖出。）

2.定义递推公式：

对于dp[i][0]。表示第 i 天持有股票所得最大现金：
如果第 i - 1天不持有股票，那么第 i 天持有股票，说明是第 i 天购入股票，此时dp[i][0] = -prices[i]
如果第 i - 1天持有股票，那么第 i 天也持有股票，说明不是第 i 天购入的，且第 i 天也没有卖出，那么金钱维持不变。dp[i][0] = dp[i - 1][0]

max(-prices[i], dp[i - 1][0])

对于dp[i][1]，表示第 i 天不持有股票所得最大现金：
如果第 i - 1天不持有股票，那么第 i 天也不持有股票，此时没有变化，dp[i][1] = dp[i - 1][1]
如果第 i - 1天持有股票，但是第 i 天不持有股票，说明是第 i 天卖出股票，此时获得收益，dp[i][1] = dp[i - 1][0] + prices[i]

max(dp[i - 1][1], dp[i - 1][0] + prices[i])

3.初始化：
dp[0][0]表示第0天持有股票所得最大现金，此时只有可能是第 0 天买的股票，不可能是前一天推出来的，所以是 -prices[0]

dp[0][1]表示第0天不持有股票所得最大现金，不可能有前一天，所以此时不持有股票就是0

4.遍历顺序：
由于后者依赖于前者，只能从前向后

5.测试：[7,1,5,3,6,4] 本题中不持有股票状态所得金钱一定比持有股票状态得到的多

class Solution {
public:
    // 动态规划
    int maxProfit(vector<int>& prices) {
        // 范围检查：下面代码要求至少一个元素
        int prices_size = prices.size();
        if (prices_size == 0) return 0;

        // 定义dp数组和初始化
        // dp[i][0]表示第i天持有股票的利润
        // dp[i][1]表示第i天不持有股票的利润
        vector<vector<int>> dp(prices_size, vector{0, 0});
        dp[0][0] = -prices[0]; // 第0天持有股票
        dp[0][1] = 0; // 第0天不持有股票

        // 遍历每一天
        for (int i = 1; i < prices_size; i++) {
            dp[i][0] = max(-prices[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]);
        }

        return dp[prices_size-1][1];
    }
};

时间复杂度O(n)， 空间复杂度O(n)，由于只依赖于前面的dp数组的两个值，所以可以改为时间复杂度为O(1)的算法。

PS:另一种定义：在这个问题中，我们可以定义一个状态 dp[i]，表示第 i 天卖出股票所能获取的最大利润。

接下来，我们考虑状态 dp[i] 和前一天的状态 dp[i-1] 之间的关系。当我们在第 i 天卖出股票时，我们可以选择在前面的某一天买入股票，使得利润最大化。因此，我们需要找到在前 i 天中的最低股票价格 min_price，然后计算当前的利润 prices[i] - min_price。

状态转移方程可以表示为：dp[i] = max(dp[i-1], prices[i] - min_price)，其中 dp[i-1] 表示在第 i-1 天时卖出股票的最大利润，prices[i] 是第 i 天的股票价格，min_price 是前 i 天中的最低股票价格。

通过不断地更新 min_price 和计算 dp[i]，我们可以得到最终的最大利润，即 dp[n-1]，其中 n 是价格数组的长度。

买卖股票的最佳时机 II

题目：122

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

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路1：贪心：因为可以买卖任意次数，但是只能同时持有一个股票，所以可以考虑前一天买入，后一天卖出，这样，这样就能得到每一天的利润。选择利润为正的相加。

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1])…..(prices[1] - prices[0])。

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

class Solution {
public:
    // 贪心法
    int maxProfit(vector<int>& prices) {
        // 范围检查：下面的代码要求至少一个元素
        if (prices.size() == 0) return 0;

        int result = 0;
        int pre = prices[0];

        // 遍历每一天
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > pre) result += prices[i] - pre;
            pre = prices[i];
        }

        return result;
    }
};

思路2：动态规划：
(怎么想出来的：
动态规划需要找到原问题和子问题存在的关系。必须定义好原问题和子问题。
如果定义原问题是第n天能够获得的最多的利润，那么子问题就是第n-1天、第n-2天能够获得的最多的利润。
那么原问题和子问题之间有什么关系呢？或者应该如何根据子问题得到原问题呢？假设已经知道子问题的答案，那么想要求第n天的最大利润，目前只知道第n天的价格，不清楚目前是否持有股票，假如之前没有持有股票，那么此时可以选择持有或者不持有股票；假如之前持有股票，那么此时可以选择继续持有股票或者不持有股票。

经过上面分析，可以发现原问题需要维持两种状态，即持有或者不持有股票。)

1.定义dp数组和下标：
dp[i][0]：表示第 i 天持有股票的最大利润。
dp[i][1]：表示第 i 天不持有股票的最大利润。

2.递推公式：
对于dp[i][0]：
假如前一天不持有股票，此时持有股票，那么此时应该为：dp[i - 1][1] - prices[i]；
假如前一天持有股票，此时也持有股票，那么此时应该保持不变：dp[i - 1][0]；
则dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0])

对于dp[i][1]：
如果前一天不持有股票，此时也选择不持有股票，那么此时应该为：dp[i - 1][1]；
如果前一天持有股票，此时选择不持有股票，那么此时应该为：dp[i][0] + prices[i]；
则dp[i][1] = max(dp[i - 1][1]，dp[i][0] + prices[i])

3.初始化：
对于dp[0][0]：表示第0天持有股票，因为不存在前一天，所以一定是当前购入股票，因此是 -prices[0];
对于dp[0][1]：表示第0天不持有股票，所以应该为0。

4.遍历顺序：
因为后者依赖于前者，所以是从前向后

5.测试用例：
[7,1,5,3,6,4]

最后一定是不持有能够获得最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len == 0) return 0;

        // 定义dp数组和初始化
        // dp[i][0]表示第i天持有股票的最大利润
        // dp[i][1]表示第i天不持有股票的最大利润
        vector<vector<int>> dp(len, vector{0, 0});
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        // 遍历每一天
        for (int i = 1; i < len; i++) {
            dp[i][0] = max(dp[i-1][1] - prices[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]);
        }

        return dp[len-1][1];
    }
};

时间复杂度O(n)；空间复杂度O(n)，实际上后者只依赖于前者的两个数据，所以可以改为O(1)

买卖股票的最佳时机III

题目：123

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

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

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

思路：之前的动态规划数组，对于一天有两种状态，持有或者不持有股票。而由于本题限制只能买卖两次，那么对于一天来说，一共有：不操作（0）、第一次买入（1）、第一次卖出（2）、第二次买入（3）、第二次卖出（4）五种状态。

1.定义dp数组和下标含义：
dp[i][j]：j = 0，1，2，3，4：表示第 i 天处于哪种状态下持有的金钱数目

2.递推公式：
对于dp[i][0]：表示第 i 天处于什么也没干的状态，即前面几天即没买入也没卖出，那么一定是0；

对于dp[i][1]：表示第 i 天处于第一次买入状态（即有可能是前 i - 1天的任何一天买入，也有可能是第 i 天第一次买入：
如果是前 i - 1天买入，那么第 i 天什么也没做，所以是dp[i - 1][1]；
如果是第 i 天第一次买入，那么是从前一天什么也没干的状态到买入状态，即dp[i - 1][0] - prices[i]；
所以dp[i][1] = max(dp[i - 1][1]，dp[i - 1][0] - prices[i])

对于dp[i][2]：表示第 i 天处于第一次卖出状态：
如果是前 i - 1天中的某一天卖出的，那么第 i 天就什么也没干，继续沿用之前的金钱，即dp[i - 1][2]；
如果是第 i 天卖出，那么表示前 i - 1 天的状态一定是第一次买入，所以为dp[i - 1][1] + prices[i]；
所以dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])

对于dp[i][3]：表示第 i 天处于第二次买入状态：
如果是前 i - 1天中某天买入的，那么第 i 天什么都没干，继续沿用之前的金钱，即dp[i - 1][3]；
如果是第 i 天买入的，说明前面一定处于第一次卖出状态，所以为dp[i - 1][2] - prices[i]；
所以dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])

对于dp[i][4]：表示第 i 天处于第二次卖出状态：
如果是前 i - 1天中的某一天卖出的，那么第 i 天什么都没干，即dp[i - 1][4]；
如果是第 i 天卖出的，那么前面一定处于第二次买入状态，所以dp[i - 1][3] + prices[i]；
所以dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

3.初始化：
dp[0][0]：什么都不做的状态一定是0，包括dp[i][0]都应该是0；
dp[0][1]：第一天就买入，那么一定是 -prices[i]；
dp[0][2]：第一天就卖出，一定是买入之后又卖出，所以是0；
dp[0][3]：第一天就第二次买入，说明一定是第一次买入和卖出之后又买入，因此也是-prices[i]；
dp[0][4]：第一天就第二次卖出，说明一定是第一次买入和卖出之后，第二次买入又卖出，因此是0。

4.遍历顺序：
后者依赖于前者，一定是从前向后。

5.举例子：以输入[1,2,3,4,5]为例

大家可以看到红色框为最后两次卖出的状态。

现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。如果想不明白的录友也可以这么理解：如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len == 0) return 0;

        // 定义dp数组和初始化
        // dp[i][j]表示第i天处于j状态时的最大利润
        // j可以是0、1、2、3、4
        // 表示无操作、第一次买入、第一次卖出、第二次买入、第二次卖出
        vector<vector<int>> dp(len, vector<int>{0, 0, 0, 0, 0});
        // 初始化
        dp[0][0] = 0;
        dp[0][1] = dp[0][3] = -prices[0];
        dp[0][2] = dp[0][4] = 0;

        // 遍历每一天
        for (int i = 1; i < len; i++) {
            dp[i][0] = 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[len-1][4];
    }
};

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

买卖股票的最佳时机IV

题目：188

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

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

思路：与上一题类似，上一题是最多买卖2次，这里是最多买卖k次，因此只是每一天的状态数目不同。

1.确定dp数组和下标定义：
dp[i][2 * j + 1]表示第 i 天处于第 j 次买入状态拥有的金钱数目；
dp[i][2 * j + 2]表示第 i 天处于第 j 次卖出状态拥有的金钱数目；
其中 j 的范围是 [0, k)

2.递推公式：

// 更新第 j 次的买入状态
dp[i][j * 2 + 1] = max(dp[i - 1][j * 2 + 1], dp[i][j * 2] - prices[i]);
// 更新第 j 次的卖出状态
dp[i][j * 2 + 2] = max(dp[i - 1][j * 2 + 2], dp[i][j * 2 + 1] + prices[i]);

3.初始化：

dp[0][j * 2 + 1]：买入状态都为 -prices[i]，表示在一天内前面j-1次都买入之后又卖出，第j次买入；
dp[0][j * 2 + 1]：卖出状态都为0，表示第一天前面j-1次都买入之后又卖出，第j次也是买入又卖出，因此没有花钱。

4.遍历顺序：
从前向后

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int len = prices.size();
        if (len == 0) return 0;

        // 定义dp数组
        int status = k*2 + 1;
        vector<vector<int>> dp(len, vector<int>(status, 0));
        // 初始化
        for (int i = 1; i < status; i += 2) dp[0][i] = -prices[0];

        // 遍历每一天
        for (int i = 1; i < len; i++) {
            dp[i][0] = 0;
            // 遍历每一种状态
            for (int j = 1; j < status; j += 2) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
                dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] + prices[i]);
            }
        }

        return dp[len-1][status-1];
    }
};

时间复杂度O(n * k)；空间复杂度O(n * k)

买卖股票的最佳时机含冷冻期

题目：309

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

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

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

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

思路：这里可以多次进行买和卖，但是卖出之后第二天不能买，因此需要细分一天的状态，尤其是处理卖出股票和冷冻期状态。需要保持的状态有：持有股票的状态，卖出股票状态（前面卖出而非今天卖出），今天卖出股票状态，冷冻期状态。区分出两种卖出状态是为了方便更新冷冻期状态，冷冻期状态只能由昨天是卖出状态来更新，因此将卖出区分为前几天卖出和今天卖出。

最后结果是取 状态二，状态三，和状态四的最大值，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

1.定义dp数组和下标含义：
dp[i][0]：表示第 i 天处于持有股票状态；
dp[i][1]：表示第 i 天处于卖出股票状态（昨天卖出已经由冷冻期表示，因此这里只能是前一天卖出或者前两天卖出）；
dp[i][2]：表示第 i 天处于今天卖出状态；
dp[i][3]：表示第 i 天处于冷冻期状态（昨天卖出）

2.递推公式：

对于dp[i][0]：
如果是前面买入，那么表示第 i 天没有进行操作，所以为dp[i - 1][0]；
如果是今天买入，说明前面处于卖出状态（前一天卖出或者前两天卖出）或者冷冻期状态（昨天卖出），所以要么是dp[i - 1][1] - prices[i]，要么是dp[i - 1][3] - prices[i]；
所以dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i])

对于dp[i][1]：（不能是昨天卖出）
如果是前天卖出的股票，那么昨天一定是冷冻期，所以是dp[i - 1][3]；
如果是前两天卖出的股票，那么昨天一定是处于第二种状态（要么前一天卖出，要么前两天卖出），所以就是dp[i - 1][1]；
所以dp[i][1] = max(dp[i - 1][3], dp[i - 1][1])

对于dp[i][2]：
表示第 i 天卖出，那么第 i - 1天一定是持有股票状态，所以dp[i][2] = dp[i - 1][0] + prices[i]

对于dp[i][3]：
表示第 i 天处于冷冻期，那么第 i - 1 天一定是处于”当天卖出状态“，所以dp[i][3] = dp[i - 1][2]

3.初始化：
对于dp[0][0]，表示第0天买入，则为 -prices[i]；
对于dp[0][1]，表示非第0天卖出，这里很难从定义上理解，只能从递推公式上看需要这个值为多少，如果i为1，第1天买入股票，那么递归公式中需要计算 dp[i - 1][1] - prices[i] ，即 dp[0][1] - prices[1]，那么大家感受一下 dp[0][1] （即第0天的状态二）应该初始成多少，只能初始为0。想一想如果初始为其他数值，是我们第1天买入股票后 手里还剩的现金数量是不是就不对了。
对于dp[0][2]，表示第0天买入之后又卖出，那么此时为0；
对于dp[0][3]，同dp[0][1]

4.遍历顺序：
从前向后

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len == 0) return 0;

        // 定义dp数组和初始化
        vector<vector<int>> dp(len, vector<int>{0, 0, 0, 0});
        // 初始化
        dp[0][0] = -prices[0]; // 处于持有股票状态
        
        // 遍历每一天
        for (int i = 1; i < len; 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][3], dp[i-1][1]);
            dp[i][2] = dp[i-1][0] + prices[i];
            dp[i][3] = dp[i-1][2];
        }

        //
        return max(dp[len-1][1], max(dp[len-1][2], dp[len-1][3]));
    }
};

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

买卖股票的最佳时机含手续费

题目：714

思路：这里买卖股票次数没有限制，但是每买卖一次就需要一次手续费，也就是在买入或者卖出时需要多支付一笔钱。

1.定义dp数组和下标含义：
dp[i][0]：表示第 i 天持有股票时拥有的金钱数目；
dp[i][1]：表示第 i 天不持有股票时拥有的金钱数目。

2.递推公式：

对于dp[i][0]：
如果前一天不持有股票，那么一定是第 i 天购入股票，所以为：dp[i - 1][1] - prices；
如果前一天持有股票，那么低 i 天什么都没做，所以为：dp[i - 1][0]
所以dp[i][0] = max(dp[i - 1][1] - prices, dp[i - 1][0])

对于dp[i][1]：
如果前一天不持有股票，那么第 i 天也不持有股票说明什么都没做，所以为：dp[i - 1][1]；
如果前一天持有股票，那么第 i 天不持有说明第 i 天卖出，另外卖出时说明一笔交易完成，需要付一笔手续费，所以为：dp[i - 1][0] + pricesp[i] - fee；
所以dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + pricesp[i] - fee)

3.初始化：
对于dp[0][0]：表示第 0天持有，由于没有前一天，一定是当天买入的，所以为 -prices[i];
对于dp[0][1]：表示第 0 天不持有，可能是没有买入没有卖出，此时为0；也有可能是买入之后卖出，多付一笔交易费fee；因此最大金额一定是不操作

4.遍历顺序：
后者依赖于前者，从前向后

5.举例子：
[1, 3, 2, 8, 4, 9], fee = 2

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int len = prices.size();
        if (len == 0) return 0;

        // 定义dp数组和初始化
        // dp[i][0]表示第i天持有股票的最大利润
        // dp[i][1]表示第i天不持有股票的最大利润
        vector<vector<int>> dp(len, vector<int>{-prices[0], 0});

        // 遍历每一天
        for (int i = 1; i < len; 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[len-1][1];
    }
};

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

股票问题总结

买卖股票的最佳时机：股票只能买卖一次，问最大利润。

【贪心解法】

取最左最小值，取最右最大值，那么得到的差值就是最大利润，代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            low = min(low, prices[i]);  // 取最左最小价格
            result = max(result, prices[i] - low); // 直接取最大区间利润
        }
        return result;
    }
};

【动态规划】

• 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])

买卖股票的最佳时机II：可以多次买卖股票，问最大收益。

【贪心解法】

收集每天的正利润便可，代码如下：

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

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

【动态规划】

dp数组定义：

• dp[i][0] 表示第i天持有股票所得现金
• dp[i][1] 表示第i天不持有股票所得最多现金

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

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]

注意这里和上一题唯一不同的地方，就是推导dp[i][0]的时候，第i天买入股票的情况。

在上一题中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。

买卖股票的最佳时机III：最多买卖两次，问最大收益。

一天一共就有五个状态，

1. 没有操作
2. 第一次买入
3. 第一次卖出
4. 第二次买入
5. 第二次卖出

买卖股票的最佳时机IV：最多买卖k笔交易，问最大收益。

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]

j的状态表示为：

• 0 表示不操作
• 1 第一次买入
• 2 第一次卖出
• 3 第二次买入
• 4 第二次卖出
• …..

除了0以外，偶数就是卖出，奇数就是买入。

最佳买卖股票时机含冷冻期：可以多次买卖但每次卖出有冷冻期1天。

dp[i][j]：第i天状态为j，所剩的最多现金为dp[i][j]。

具体可以区分出如下四个状态：

• 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
• 卖出股票状态，这里就有两种卖出股票状态
  • 状态二：两天前（前天或者前两天）就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
  • 状态三：今天卖出了股票
• 状态四：今天为冷冻期状态，表示一定是昨天卖出的股票

买卖股票的最佳时机含手续费：可以多次买卖，但每次有手续费。

本题和买卖股票的最佳时机II的区别就是这里需要多一个减去手续费的操作。

最长递增子序列

题目：300

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路：动态规划的两个典型特征，（1）子问题重叠；（2）最优子结构
如何定义原问题能够使得满足这两个性质呢？

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。

1.定义dp数组和下标定义：
如上

2.确定递推公式：
位置 i 的最长子序列一定是有前面的子问题推出，所以只要是比nums[i]小的尾元素，都可以作为 i 的子问题。如果都比nums[i]大或者等于nums[i]，那么长度只能为1。所以递推公式为：

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3.初始化：
至少都为1

4.遍历顺序：
外层循环遍历数字，内层循环遍历之前的数字

这里注意，dp[i]表示的是以nums[i]为最后一个元素的最长子序列，所以最终的结果是找所有dp中最大的。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;

        // 定义dp数组
        // dp[i]表示以下标为i的数字为结尾的最长子序列长度
        vector<int> dp(len, 1); // 最短都是一个字符的长度

        int result = 1;
        // 遍历字符
        for (int i = 0; i < len; i++) {
            // 遍历前面的元素
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) 
                    dp[i] = max(dp[i], dp[j] + 1);
            }

            // 记录最长子序列
            result = max(result, dp[i]);
        }

        return result;
    }
};

时间复杂度O(n^2)；空间复杂度O(n)

最长连续递增序列

题目：674

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

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

思路1：遍历数组，记录每一个递增子序列长度，保存下最长的记录。

int findLengthOfLCIS(vector<int>& nums) {
    if (nums.size() == 0) return 0;

    int result = 0;
    int count = 1; // 表示遍历时递增子序列长度
    int last = nums[0];

    // 遍历数组
    for (int i = 1; i < nums.size(); ++i) {
        if (last < nums[i]) {
            // 如果递增长度加1
            count++;
            last = nums[i];
        } else {
            // 此时不再是连续递增
            // 记录最长长度
            count > result ? result = count : result;

            count = 1; // 更新递增子序列长度
            last = nums[i];
        }
    }

    // 比较最后一个递增子序列长度
    count > result ? result = count : result;

    return result;
}

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

思路2：动态规划：这一题与上一题不一样的是子序列必须是连续的，不能是间隔的。

1.定义dp数组和下标：
dp[i] 表示以 nums[i] 为最后一个元素的连续递增子序列的长度

为什么这么定义？所有的连续递增子序列一定有一个尾部元素，那么分别以每个元素为尾部元素，一定可以找到所有的递增子序列。取最长的就是要找的目标。

2.递推公式：
对于dp[i] 来说，至少它自身构成了一个“连续递增序列”，如果想要构成一个以nums[i]为尾部元素的递增序列，那么nums[i]必须大于nums[i - 1]，否则就不是一个连续的序列。所以递推公式为：

if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1

3.初始化：
以每个元素为尾部元素的子序列长度至少是1

4.遍历顺序：
从前向后

5.例子：
[1,3,5,4,7]

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;

        // 定义dp数组和初始化
        // dp[i]表示以下标为i的数字为结尾的最长连续递增子序列的长度
        vector<int> dp(len, 1);

        int result = 1;
        // 遍历所有数字作为结尾
        // 下标从1开始，因为以下标为0的数字作为结尾的最长连续递增子序列只能是1
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1])
                dp[i] = dp[i - 1] + 1;
            else dp[i] = 1;

            // 记录最大值
            result = max(dp[i], result);
        }

        return result;
    }
};

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

最长重复子数组

题目：718

注意题目中说的子数组，其实就是连续子序列。

思路1：暴力解法：认为子数组指的是原数组中连续的一段数组序列，而不是间隔的子数组概念。
外层循环遍历第一个数组的所有元素作为子数组起点，中间循环遍历第二个数组与外层循环一样的元素作为起点，内层循环尝试比较二者后面的元素是否一一对应，记录下最长的长度。

优化：假设三层循环分别是i，j，k。如果已经找到了一段公共的子数组，那么此时第一个数组的[i, i + k]和第二个数组的[j,j + k]这一段都已经比较过了，所以不用再次比较；因此下一次循环时 i 直接从 i + k + 1开始
不正确，因为第二个数组中可能有多个与第一个数组起点相同的元素，比较完[i, i + k]和[j,j + k]之后，无法保证会不会存在以[i+1, i+k]为起点的元素在第二个数组中有比[j+1, j+k]这段序列更长的子序列，即在第二个数组中存在另一个 m ，使得[(i+1~i+k的其中一个元素), i+K]与[m, m+k]更长

优化：修改上面的优化，下一次循环时 j 从j+k+1开始，因为第二个数组是从前向后便利的，即使有多个与外层循环起点相同的元素，j前面的也已经比较过了；即使在[j+1, j+k]这一段中有与外层循环相同的起点元素，到i+k+1和j+k+1也一定是不同的，所以长度不会超过k，所以可以从j+k+1开始寻找外层循环的起点元素。
不正确，对于测试用例：
[0,0,0,0,0,0,1,0,0,0]
[0,0,0,0,0,0,0,1,0,0]
假设此时第一个数组的起点是第一个元素，那么当j为0时，比较到 第7个元素时不同，此时最大长度为6；根据上面的优化，此时j应该跳到7开始比较，但是实际上j为1开始比较才是最大长度9。这里的问题是，上面加粗的一段话，所以j下次循环时应该从与外层起点相同的元素开始，不能跳跃。

时间复杂度O(n^3)；空间复杂度O(1)

超时。

思路2：动态规划

定义原问题的关键在于使得原问题能够与子问题建立关系。
我的思考过程：使用dp[i]表示以nums[i]作为最后一个元素的的最大子数组长度，但是这样无法比较两个数组.

所以采用二维数组表示两个号字符串的所有比较情况。

1.定义dp数组和下标含义：
dp[i][j]表示以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]

(为什么不定义成 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度？如果定义 dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，那么 第一行和第一列要进行初始化，如果nums1[i] 与 nums2[0] 相同的话，对应的 dp[i][0]就要初始为1， 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话，同理。)

2.递推公式：
对于dp[i][j]是要由前面的推出，如果nums[i - 1] == nums[j - 1]，那么（注意i 和 j 都要从1开始）

p[i][j] = dp[i - 1][j - 1] + 1

3.初始化：
dp[i][0]（第一列）和dp[0][j]（第一行）都是没有意义的，因为i 和 j 都从1开始。但是由于需要dp[i][0] 和dp[0][j] + 1所以都初始化为0

4.遍历顺序：
需要两层循环，只要保证两层循环都是从前向后即可。

5.测试例子：

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        // 边界检查：如果任一数组为空应该返回0
        if (len1 == 0 || len2 == 0) return 0;

        // 定义dp数组和初始化
        // dp[i][j]表示以第i-1下标结尾的nums1和以第j-1下标结尾的nums2
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

        int result = 0;
        // 遍历
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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;
    }
};

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

另一种定义方式，dp[i][j]表示以A中下标为i的数字结尾，B中下标为J的数字结尾的最长子数组长度。

此时需要初始化第一行和第一列：如果字符相同则初始化为1；

另外遍历时也需要从0开始而不是1，这是因为result要记录所有答案；如果不想这样做就需要在初始化时也将result记录。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        // 边界检查：如果均为空数组或者某一个为空数组
        if (len1 == 0 || len2 == 0) return 0;

        // 定义dp数组
        // dp[i][j]表示范围[0, i]的第一个数组
        // 和范围[0, j]的第二个数组之间的最长重复子数组长度
        vector<vector<int>> dp(len1, vector<int>(len2, 0));
        // 初始化行
        for (int j = 0; j < len2; j++) {
            if (nums2[j] == nums1[0])
                dp[0][j] = 1;

        }
        // 初始化列
        for (int i = 0; i < len1; i++) {
            if (nums1[i] == nums2[0]) 
                dp[i][0] = 1;
        }

        int result = 0;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (nums1[i] == nums2[j] && i > 0 && j > 0) 
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                result = max(result, dp[i][j]);
            }

        }

        return result;
    }
};

最长公共子序列

题目：1143

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路：这里的子序列并不要求连续，上一题的子数组要求是连续的。

参考上一题的思路，定义dp[i][j]表示长度为[0, i]的字符串A，和长度为[0, j]字符串B最长公共子序列的长度

2.递推公式：
如果A[i] == B[j]，那么找到了一个公共元素，此时应该为dp[i - 1][j - 1] + 1。
如果A[i] != B[j]，那么就需要从A的[0, i - 1]与B的[0, j]的最长子序列，和A的[0, i]与B的[0, j - 1]的最长子序列中选择一个较大的。所以为max(dp[i - 1][j]，dp[i][j - 1])

3.初始化：
dp[i][0]表示长度为[0, i]的字符串A，可长度为下标 0 的字符串B的最长公共字串，那就是如果发现相等后面就都为1，否则就为0；
dp[0][j]同理。

4.遍历顺序：
后者依赖于左上、左边、上面元素，所以从左到右的顺序、从上到下的顺序。

5.例子：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        // 边界检查：任一为空应该返回0
        if (len1 == 0 || len2 == 0) return 0;

        // 定义dp数组和初始化
        vector<vector<int>> dp(len1, vector<int>(len2, 0));

        int result = 0;
        // 初始化行
        for (int j = 0; j < len2; j++) {
            if (text1[0] == text2[j]) {
                while (j < len2) dp[0][j++] = 1;

                result = 1;
                break;
            }
        }
        // 初始化列
        for (int i = 0; i < len1; i++) {
            if (text1[i] == text2[0]) {
                // 将后面全部初始化为1
                while (i < len1) dp[i++][0] = 1;

                result = 1;
                break;
            }
        }

        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (text1[i] == text2[j]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);

                result = max(result, dp[i][j]);
            }
        }

        return result;
    }
};

时间复杂度O(nm)；空间复杂度O(nm)

另一种定义方式：dp[i][j]表示范围为[0, i-1]的S串和范围为[0, j-1]的T串的最长公共子序列。

这里的初始化：dp[i][0]和dp[0][j]没有意义，但是后面需要用到它们，所以初始化为0.

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        // 边界检查：任一为空应该返回0
        if (len1 == 0 || len2 == 0) return 0;

        // 定义dp数组和初始化
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

        int result = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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]);

                result = max(result, dp[i][j]);
            }
        }

        return result;
    }
};

不相交的线

题目：1035

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

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

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

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

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

思路：动态规划：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

1.定义dp数组和下标含义：
dp[i][j]表示长度为[0, i]的第一个数组和长度为[0, j]的第二个数组的最大连线数目

2.递推公式：
如果第一个数组的A[i] == 第二个数组B[j]，那么此时连线数目应该加1，能够保证不会出现交叉，所以为dp[i - 1][j - 1] + 1；
如果不等，让长度为[0, i - 1]的第一个数组与长度为[0, j]的第二个数组比较，寻找最大连线数目；在让长度为[0, i]的第一个数组和长度为[0, j - 1]的第二个数组比较，寻找最大连线数目。此时取二者较大的哪一个。即max(dp[i - 1][j], dp[i][j - 1])

3.初始化：
dp[i][0]表示长度为[0, i]的第一个数组与长度为只有一个元素的第二个数组的最大连线数目，如果发现 A[i] == B[0]，那么下标 i 之后的数组至少都会有 i 与第二个数组的第一个元素有连线，所以后面都为1；
dp[0][j]同理。

4.遍历顺序：
从前向后（内循环）；从上到下（外循环）

5.例子：

时间复杂度O(nm)；空间复杂度O(nm)

代码与上一题一致。

下面给出另一种定义方式的代码：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        // 边界检查：任一数组为空返回0
        if (len1 == 0 || len2 == 0) return 0;

        // 定义dp数组和初始化
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

        int result = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <=len2; 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]);

                result = max(result, dp[i][j]);
            }
        }

        return result;
    }
};

最大子数组和

题目：53

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

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

思路1：题目要求子数组必须是一段连续部分。

暴力解法：从前向后遍历数组，分别以每一个元素作为起点，然后向后遍历元素，记录最大值。
时间复杂度O(n ^ 2)。

思路2：贪心算法：如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int count = 0;
        int result = INT_MIN; // 防止都是负数

        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            
            // 记录连续长度
            result = max(result, count);

            // 如果这一段连续和小于0那就放弃
            if (count < 0) count = 0;
        }

        return result;
    }
};

时间复杂度O(n)

思路3：动态规划：

1.定义dp数组和下标：
dp[i]表示以 i为最后一个元素的连续子数组的最大和。

2.确定递推公式：
要么dp[i - 1] + nums[i]，要么只能是nums[i]。
因此递推公式就是max(dp[i - 1] + nums[i], nums[i])

3.初始化：
dp[0]只能是第一个元素

4.遍历顺序：
从前向后

5.例子：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        // 边界检查：如果数组为空返回0
        if (len == 0) return 0;

        // 定义dp数组和初始化
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];

        int result = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = max(result, dp[i]);
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)，但是由于只依赖与前面一个元素，所以可以降到O(1)

子数组、子序列问题总结

不连续：

最长递增子序列：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。这里子序列是非连续的。
这里将原问题定义为以第 n 个字符为结尾元素的子序列的长度，这样定义是为了方便递推，所有的自问题就是分别以[0, n - 1]下标对应的字符作为结尾元素的子序列长度，例如如果已经知道以第 n - 1个字符为结尾i元素的子序列长度，那么只需判断第 n 个字符与第 n - 1个字符的关系，就可以判断是否将长度加 1.那么遍历以第[0, n -1]个字符结尾的子序列长度，以最大的作为原问题的解。

如果将原问题定义为n个字符的数组最长的子序列长度，那么是没有办法从子问题中推出原问题的，因为连最后一个元素是什么都不知道，现在增加一个元素，怎么知道是否是递增的呢。

递推公式：

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

最长公共子序列：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
这里将原问题定义为：dp[i][j]表示长度为[0, i]的S串和长度为[0, j]的T串之间的最长公共子序列长度。这样子问题就是所有长度小于 i 和长度小于 j 的S串和T串的最长公共子序列长度。

递推公式：如果S[i] 与T[j]相等，那么明显是在[0, i - 1]的S串和[0, j - 1]的T串的最长公共子序列长度上加1；
如果不等，那么考虑长度为[0, i - 1]的S串与[0, j]的T串的最长公共子序列，和长度为[0, i]的S串与[0, j - 1]的T串的最长公共子序列，取二者中较大的。

if (text1[i - 1] == text2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

不相交的线：

绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

连续：

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

将原问题定义为以下标i为结尾的连续递增的子序列长度为dp[i]。这样定义也是因为能够从子问题推出原问题。

如果定义时没有确定结尾元素的位置，那么无法通过新元素与结尾元素的比较确定子序列是否需要加1.

递推公式：这里因为是连续，所以只能从第 n - 1的子问题上推出，其它的子问题就算添加第 n个元素也是不连续的。

dp[i] = dp[i - 1] + 1

最长重复子数组：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。题目中说的子数组，其实就是连续子序列。

原问题定义为：dp[i][j]以下标i结尾的A，和以下标j为结尾的B，最长重复子数组长度，其实类似于连续递增子序列的思路，这样就可以通过比较A[i]和B[j]是否相同来判断连续相同子序列长度是否应该加1.

if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;

最大子序和：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

因为是连续，需要最后一个元素的位置信息，所以原问题定义为包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。

因为是连续子序列和，要么将第 i 个元素加入dp[i - 1]的子序列和，要么就只能重新还是计算子序列，也就是nums[i]

dp[i] = max(dp[i - 1] + nums[i], nums[i])

判断子序列

题目：392

思路1：暴力法：从前向后遍历字符串s，遍历字符串t查找。

时间复杂度最差就是遍历t串中所有元素。空间复杂度O(1)

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int len1 = s.length();
        int len2 = t.length();
        // 边界检查：两个都为空返回true
        // s为空返回true

        int i = 0, j = 0;
        while (i < len1) {
            while (j < len2 && s[i] != t[j]) j++;

            // 如果循环结束j已经超出范围
            if (j == len2) return false;

            // 比较下一个字符
            i++;
            j++; 
        }

        return true;
    }
};

思路2：之前曾经做过求两个字符串的最大公共子序列的长度，如果最终求出的最大长度为S串的长度，说明S串就是T串的子序列。

1.定义dp数组和下标：
dp[i][j]表示长度为[0, i]的S串和长度为[0, j]的T串的最大公共子序列的长度

2.递推公式：
如果S[i] == T[j]，那么长度应该为dp[i - 1][j - 1] + 1；
如果不等，那么长度应该从：长度为[0, i - 1]的S串和长度为[0, j]的T串的最长公共子序列长度，长度为[0, i]的S串和长度为[0, j - 1]的T串的最长公共子序列长度，二者中选择较大的。

3.初始化：
对于dp[i][0]，如果找到S[i] == T[0]，那么长度大于等于 i 的S串都应该至少有一个字符与T串相等；
dp[0][j]同理。

4.遍历顺序：
从左到右，从上到下。

（这里的给的代码是另一种定义，即dp[i][j]表示长度为[0, i]的S串和长度为[0, j]的T串的最大公共子序列的长度，省去了初始化）

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int len1 = s.length();
        int len2 = t.length();

        // 定义dp数组和初始化
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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]);
            }
        }

        // 判断最长公共子序列长度是否为s串长度
        if (len1 == dp[len1][len2]) return true;
        else return false;
    }
};

时间复杂度O(nm)，实际上是小于这个值的，这里做了优化是外层循环遍历的是T串，这样如果能够T串早就能够满足S串，就会提前返回结果；空间复杂度O(nm)

思路3：同样是动态规划，但是作者的定义方式不同：与上面类似，均是求出子序列长度最后等于S串长度说明就是可以找到

1.dp数组和下标含义：
dp[i][j]表示以S[i]为结尾元素字符串和以T[i]为结尾元素的字符串相同的子序列长度

2.递推公式：
如果S[i] == T[j]，那么最长序列长度应该加1，即dp[i - 1][j - 1] + 1；
否则，说明T[i]不在S串中，应该删除这个元素，即dp[i][j - 1]；

3.初始化：（这里做一下优化，i表示T串，能够提前结束）
与上面一致。

4.遍历顺序：
选择外层循环遍历T串，这样如果提前能够找到S串作为子序列，那么就可以提前结束。

（同样给出另一种定义的方法，省去初始化）

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int len1 = s.length();
        int len2 = t.length();

        // 定义dp数组和初始化
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

        // 遍历
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i - 1] == t[j - 1]) {
                    // 两个字符匹配
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 不匹配，应该将t串的字符删除
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        // 判断子序列长度是否满足
        if (len1 == dp[len1][len2]) return true;
        else return false;
    }
};

时间复杂度O(nm)；空间复杂度O(nm)

不同的子序列

题目：115

思路1：仍然采用双指针思路，只是遍历完T串之后计数一次，然后从头开始。

这是错误的，因为题目中并不是先找到一个T串之后再从剩下的序列中再次尝试找T串。

思路2：动态规划

1.定义dp数组和下标含义：
dp[i][j]表示以S[i]结尾的S串子序列与以T[j]结尾的T串（注意不应该是T串子序列，而是以整个T串），T串在S串的子序列中出现的个数

2.递推公式：
如果S[i] == T[j]，那么可以使用S[i]进行匹配，即不需要考虑当前s子串和t子串的最后一位字母，那么个数为dp[i - 1][j -1]；也可以使用S[i - 1]进行匹配，那么个数为dp[i - 1][j]。比如bagg和bag，既可以使用S串第四个元素g，也可以使用S串的第三个元素g匹配bag的g。
所以是dp[i - 1][j - 1] + dp[i - 1][j]

如果不等，那么只能尝试使用S[i - 1]进行匹配，即相当于删除S[i]元素。所以是dp[i - 1][j]

3.初始化：
每次需要用到左上角和上边元素，因此第一行和第一列必须初始化。
对于dp[i][0]，如果出现S[i] == T[0]，那么此时dp[i][0]应该是上一次出现相等的次数 + 1（表示以S[i]结尾的S串子序列可以删除任意元素变成T[0]的次数加1），中间不等的部分就是上一次相等的次数；
对于dp[0][j]，表示长度只有1的S串可以任意删除元素，与[0, j]的T串进行匹配，T串长度大于S串，因此不可能出现在S串中，均为0.

4.遍历顺序：
从前向后，从上到下

class Solution {
public:
    int numDistinct(string s, string t) {
        if (t.size() == 0) return -1; // 如果目标串是空，那么应该是未定义操作
        else if (s.size() == 0) return 0;

        // 定义dp数组
        vector<vector<int>> dp(s.size(), vector<int>(t.size(), 0));
        // 初始化第一列
        int last = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == t[0]) dp[i][0] = ++last;
            else dp[i][0] = last;
        }
        // // 初始化第一行
        // for (int j = 0; j < t.size(); j++) {
        //     if (s[0] == t[j]) dp[0][j] = 1;
        // }

        for (int i = 1; i < s.size(); i++) {
            for (int j = 1; j < t.size(); j++) {
                if (s[i] == t[j]) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % static_cast<int>(1e9 + 7);
                else dp[i][j] = dp[i - 1][j];
            }
        }

        return dp[s.size() - 1][t.size() - 1];
    }
};

时间复杂度O(nm)；空间复杂度O(nm)

补充：对结果取模10^9 + 7的操作

首先int的范围是2 * 10 ^ 9，其次取模的操作应该是这种形式：

count = (count + n) % static_cast<int>(1e9 + 7)

等式右边两个int相加需要不超过一个int

另一种定义方式：dp[i][j]表示以S[i-1]结尾的S串的子序列中出现以T[j-1]结尾的子串的次数

注意初始化：

class Solution {
public:
    int numDistinct(string s, string t) {
        int len1 = s.length();
        int len2 = t.length();

        // 定义dp数组和初始化
        // dp[i][j]表示以S[i-1]结尾的子序列中
        // T[0, j-1]整个字符串出现的次数
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        // 初始化
        // dp[i][0]表示以S[i-1]结尾的子序列中任意删除元素，变为空串的方法
        for (int i = 0; i <= len1; i++) dp[i][0] = 1;
        // dp[0][j]表示从空串S中删除元素变为t串的方法
        for (int j = 0; j <= len2; j++) dp[0][j] = 0;
        // dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
        dp[0][0] = 1;

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s[i - 1] == t[j - 1]) {
                    // 此时可以使用S[0, i-2]的子序列匹配T[0, j-2]，不需要考虑当前s子串和t子串的最后一位字母
                    // 于是就是dp[i - 1][j - 1]
                    // 也可以使用S[0, i-2]的子序列进行匹配T[0, j-1]，不考虑s串的最后一个字母
                    // 于是就是dp[i - 1][j]
                    dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % static_cast<int>(1e9 + 7);
                } else {
                    // 此时只能S[0, i-2]匹配T[0, j-1]，不考虑s串的最后一个字母，相当于删除
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[len1][len2];
    }
};

两个字符串的删除操作

题目：583

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

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

思路：动态规划

1.定义dp数组和下标含义：
dp[i][j]：表示长度为[0, i]的S串与长度为[0, j]的T串相同所需最小步数。

2.递推公式：
如果S[i] == T[j]，那么不需要进行删除操作，只需要令[0, i - 1]和[0, j - 1]相等即可，所以为dp[i - 1][j - 1]：
如果不等，那么有两种方式：第一种是删除S串的最后一个元素，即令[0, i - 1]与[0, j]相等，此时为dp[i - 1][j] + 1，第二种方式是删除T串的最后一个元素，即令[0, i]与[0, j - 1]相等，此时为dp[i][j - 1] + 1，取两种方式中最小的。
PS:应该还存在一种情况，就是删除S串的最后一个元素和删除T串的最后一个元素，即dp[i - 1][j - 1] + 2。但是这种情况可以这么理解：dp[i - 1][j]表示不考虑S串的最后一个元素，如果再删除一个T串的最后一个元素，那么相当于同时删除了S串和T串的最后一个元素，即为dp[i - 1][j] + 1。

3.初始化：
首先是dp[0][0]，表示只有一个元素的S串和T串，如果相等，那么无需操作，即为0；否则需要删除S串的一个元素，删除T串唯一元素，让两者都成为空串就像等，即为2；
其次是对于dp[i][0]，表示长度为[0, i]的S串与只有一个元素的T串变成相等需要的操作数，假如当前S串下标为 i ，如果S[i]与T[0]相等，就需要删除S串中前面的所有元素，dp[i][0] = i；如果不等，就是dp[i + 1][0] + 1，表示删除这个i之后与T串相等的操作数。

4.遍历顺序：
从上到下，从左到右

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();

        // 定义dp数组
        // dp[i][j]表示S[0, i]和T[0, j]相同所需最小步数
        vector<vector<int>> dp(len1, vector<int>(len2, 0));
        // 初始化
        // dp[0][0]
        if (word1[0] == word2[0]) dp[0][0] = 0;
        else dp[0][0] = 2;

        // dp[i][0]表示S[0, i]和T[0]相同所需最小步数
        // 如S[i]与T[0]相同应该删除前面所有元素
        for (int i = 1; i < len1; i++) {
            if (word1[i] == word2[0]) dp[i][0] = i;
            else dp[i][0] = dp[i - 1][0] + 1;
        }

        // dp[0][j]表示S[0]与T[0, j]相同所需最小步数
        for (int j = 1; j < len2; j++) {
            if (word1[0] == word2[j]) dp[0][j] = j;
            else dp[0][j] = dp[0][j - 1] + 1;
        }

        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (word1[i] == word2[j]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }

        return dp[len1 - 1][len2 - 1];
    }
};

时间复杂度O(nm)；空间复杂度O(nm)

另一种定义方式：dp[i][j] 表示以下标i-1结尾的S串和以下标j-1结尾的T串，所需删除元素的最小次数

递推公式不变，初始化需要注意：

dp[0][0]表示两个空串相等需要的操作数，应该为0；

dp[i][0]表示以S[i - 1]结尾的字符串与空串相等所需要次数，应该是i；

dp[0][j]表示以T[j - 1]结尾的字符串与空串相等所需次数，应该是j

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();

        // 定义dp数组
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        dp[0][0] = 0;
        for (int i = 1; i <= len1; i++) dp[i][0] = i;
        for (int j = 1; j <= len2; j++) dp[0][j] = j;

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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], dp[i][j - 1]) + 1;
            }
        }

        return dp[len1][len2];
    }
};

思路2：另一种动态规划：
只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

编辑距离

题目：72

思路：动态规划

这一题与上一题类似，对于原问题的定义都是类似的。问题是，如何理解动态数组的定义之后得到递推公式。

1.定义dp数组和下标含义：
dp[i][j]：表示长度为[0, i]的S串与长度为[0, j]的T串相同所需最小步数。

2.递推公式：
如果S[i] == T[j]，那么对于这个位置的字符不用再调整，只需要调整S串的[0, i - 1]部分和T串的[0, j - 1]部分，使得两者相同，那么长度为[0, i]的S串和长度为[0, j]的T串自然就相等了（将原问题转换为子问题），即dp[i - 1][j - 1]；
如果不等，那么可以采取三种操作：删除、插入、替换：
首先是删除：因为是让S串变成T串，所以如果第 i 个字符与T的第 j 个字符不等，那就尝试删除第 i 个字符，调整[0, i - 1]使得与[0, j]相等（换一个方向理解，自下而上去理解，就是如果经过调整之后[0, i - 1]S串与[0, j]T串相等，那么再删除第 i 个字符就可以使得[0, i]S串与T串相等），所以是dp[i - 1][j] + 1;
接着是添加：这里需要换一个角度理解，S串添加一个元素才能与T串相等，其实就是T串删除一个元素之后与S串相等。例如S串为a，T串为ab，那么S串添加一个字符的操作之后与T串相等，其实就相当于T串删除一个元素之后与S串相等。所以为dp[i][j - 1] + 1。自下而上理解就是，如果长度为[0, i]的S串经过调整之后与[0, j - 1]的T串已经相等，那么对于长度为[0, j]的T串来说只需再删除最后一个元素即可。
最后是替换：如果最后一个元素不相等，只需要令S串的最后一个元素替换成T串的最后一个元素即可，也就是假如经过调整之后[0, i - 1]已经与[0, j - 1]相等，那么只需再做一次替换操作就可以使得长度为[0, i]与长度为[0, j]相等，所以是dp[i - 1][j - 1] + 1。

3.初始化：
从递推公式可以看出依赖于左上、左边和上边元素，因此需要初始化第一行、第一列。
首先是dp[0][0]，如果相等就是0，否则就是执行一步替换操作为1。
首先是第一列：dp[i][0]，表示长度为[0, i]的S串最少经过多少次调整与一个字符T[0]相等。如果S[i]与T[0]相等，那么把[0, i-i]全部删除，操作数是 i；如果不等，那就只能从上面一个元素推出，也就是多进行一步删除操作。
最后是第一行：dp[0][j]，如果S[0]与T[j]相等，那么需要添加[0, j - 1]一共 j 个元素；如果不等，只能从前一个元素推出，多添加一个元素。

4.遍历顺序：
从前向后，从上到下

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        // 边界检查：如果S串为空返回T串长度
        if (len1 == 0) return len2;
        // 如果T串为空返回S串长度
        if (len2 == 0) return len1;

        // 定义dp数组和初始化
        vector<vector<int>> dp(len1, vector<int>(len2, 0));
        // 初始化
        // dp[0][0]表示一个字符S[0]与一个字符T[0]相等所需最少操作数
        if (word1[0] == word2[0]) dp[0][0] = 0;
        else dp[0][0] = 1;
        // dp[i][0]表示以下标i结尾的S串与一个字符T[0]相等所需最少操作数
        for (int i = 1; i < len1; i++) {
            if (word1[i] == word2[0]) dp[i][0] = i;
            else dp[i][0] = dp[i - 1][0] + 1;
        }
        // dp[0][j]表示S[0]一个字符如何与以j结尾的T串相等
        for (int j = 1; j < len2; j++) {
            if (word1[0] == word2[j]) dp[0][j] = j;
            else dp[0][j] = dp[0][j - 1] + 1;
        }

        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (word1[i] == word2[j]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }

        return dp[len1 - 1][len2 - 1];
    }
};

时间复杂度O(nm)；空间复杂度O(nm)

另一种定义方式：dp[i][j]表示以i-1结尾的S串和以j-1结尾的T串，S串变成T串所需最小操作数

递推公式不变，初始化：

dp[0][0]表示两个空串相等所需操作数，应该是0；

dp[i][0]表示以下标i -1结尾的S串变成空串所需操作数，应该是i，表示删除i个元素；

dp[0][j]表示空串S变成以下标j-1结尾的T串所需操作数，应该是j，表示添加j个元素

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        // 边界检查：如果S串为空返回T串长度
        if (len1 == 0) return len2;
        // 如果T串为空返回S串长度
        if (len2 == 0) return len1;

        // 定义dp数组和初始化
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        // 初始化
        // dp[0][0]表示一个字符S[0]与一个字符T[0]相等所需最少操作数
        dp[0][0] = 0;
        for (int i = 1; i <= len1; i++) dp[i][0] = i;
        for (int j = 1; j <= len2; j++) dp[0][j] = j;


        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }

        return dp[len1][len2];
    }
};

编辑距离总结

判断子序列：给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
这一道题原问题定义为S[0, i]和T[0, j]的子序列长度。如果最后一个字符相等，那么相同子序列长度加1；否则在T串中删除最后一个元素（自下而上理解，就是已知[0, i]与[0, j - 1]的最长子序列长度，如果S[i]与S[j]不相等，那么[0, i]和[0, j]的最长子序列与子问题相同）
状态转移方程：

if (t[i] == s[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i - 1][j]; // 删除S的最后一个元素

不同的子序列：给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
原问题定义不变。

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。 相当于删除S串的最后一个元素。
这里可能有同学不明白了，为什么还要考虑 不用s[i - 1]来匹配，都相同了指定要匹配啊。
例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。
当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。
所以当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];

状态转移方程为：
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];
}

两个字符串的删除操作：给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最少步数，每步可以删除任意一个字符串中的一个字符。
与上一题相比，就是两个字符串都可以进行删除操作

编辑距离：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

回文子串

题目：647

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

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

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

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

思路1：暴力法：即遍历每一个字串，也就是使用双循环找到不同起点和不同终点的字串，再判断是否为回文串，这样时间复杂度为O(n ^ 3），大概率会超时

思路2：动态规划

1.确定dp数组：

如果定义原问题为以下标为 i 字符结尾的回文子串的数目，那么很难找到递归关系。

分析问题，如图：

我们在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。

那么此时我们是不是能找到一种递归关系，也就是判断一个子字符串（字符串的下表范围[i,j]）是否回文，依赖于，子字符串（下表范围[i + 1, j - 1]）） 是否是回文。

所以为了明确这种递归关系，我们的dp数组是要定义成一位二维dp数组。

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2.递推公式：

如果S[i]与S[j]不等，那么一定不是回文串；
如果相等：首先判断 i 是否与 j 相等，也就是同一个字符，如果是就是回文字串；
接着判断i 与 j是否相差1，如果相差为1，那么也是回文串；
最后相差大于1的时候，需要根据dp[i + 1][j - 1]判断是否为回文串。

3.初始化：

初始化为false

4.遍历顺序：

由于依赖于左下角的元素，左移必须从下到上，从左到右

注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。

时间复杂度O(n ^ 2)；空间复杂度O(n ^ 2)

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length();
        // 边界检查：
        if (len == 0 || len == 1) return true;

        // 定义dp数组和初始化
        // dp[i][j]表示区间范围为[i, j]的字符串是否为回文串
        vector<vector<bool>> dp(len, vector<bool>(len, false));

        int count = 0;
        // 遍历顺序从下到上
        for (int i = len-1; i >= 0; i--) {
            for (int j = 0; j < len; j++) {
                if (j < i) continue;

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    // 两段字母相等
                    if (i == j || j - i == 1) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }

                if (dp[i][j]) count++;
            }
        }

        return count;
    }
};

思路3：双指针法

动态规划的空间复杂度是偏高的，我们再看一下双指针法。

首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。

在遍历中心点的时候，要注意中心点有两种情况。

一个元素可以作为中心点，两个元素也可以作为中心点。

那么有人问了，三个元素还可以做中心点呢。其实三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到。

所以我们在计算的时候，要注意一个元素为中心点和两个元素为中心点的情况。

这两种情况可以放在一起计算，但分别计算思路更清晰，我倾向于分别计算，代码如下：

class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            result += extend(s, i, i, s.size()); // 以i为中心
            result += extend(s, i, i + 1, s.size()); // 以i和i+1为中心
        }
        return result;
    }
    int extend(const string& s, int i, int j, int n) {
        int res = 0;
        while (i >= 0 && j < n && s[i] == s[j]) {
            i--;
            j++;
            res++;
        }
        return res;
    }
};

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

回文子序列

题目：516

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

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

思路：动态规划（上一题求的是回文子串，这一题求的是回文子序列）

1.dp数组定义
**字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]**。

2.递推公式：
这里因为是子序列而不是字串，不要求连续，所以递推公式有所区别
如果 S[i]等于S[j]那么长度加2，即dp[i + 1][j - 1] + 2；
如果不等，说明同时加上两个字符不能增加长度，所以尝试单独加上一个：即dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

3.初始化：首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])中dp[i][j]才不会被初始值覆盖。

4.遍历顺序：
从下到上，从左到右

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        if (len == 0) return 0;

        // 定义dp数组
        // dp[i][j]表示[i, j]范围内最长的回文子序列长度
        vector<vector<int>> dp(len, vector<int>(len, 0));
        // 初始化i与j相同的情况
        for (int i = 0; i < len; i++) dp[i][i] = 1;

        // 从下到上遍历
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; 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][len - 1];
    }
};

时间复杂度O(n ^ 2)；空间复杂度O(n ^ 2)

动态规划总结

动态规划基础：
斐波那契数
爬楼梯
使用最小花费爬楼梯
不同路径
不同路径还不够，要有障碍！
整数拆分
不同的二叉搜索树

背包问题：

打家劫舍系列

股票系列：

子序列系列：