动态规划

思考这三个问题：
动态规划的解题步骤

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

思考这三个问题：

这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？
动态规划的解题步骤

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

一、斐波那契数，

通常⽤ F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后⾯的每⼀项数字都是前⾯两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。 示例 1：输⼊：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2：输⼊：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3：输⼊：4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3 提示：0 <= n <= 30

斐波那契数列⼤家应该⾮常熟悉不过了，⾮常适合作为动规第⼀道题⽬来练练⼿。因为这道题⽬⽐较简单，可能⼀些同学并不需要做什么分析，直接顺⼿⼀写就过了。     但「代码随想录」的⻛格是：简单题⽬是⽤来加深对解题⽅法论的理解的。<br />通过这道题⽬让⼤家可以初步认识到，按照动规五部曲是如何解题的。<br />对于动规，如果没有⽅法论的话，可能简单题⽬可以顺⼿⼀写就过，难⼀点就不知道如何下⼿了。<br />所以我总结的动规五部曲，是要⽤来贯穿整个动态规划系列的，就像之前讲过⼆叉树系列的递归三部       曲，回溯法系列的回溯三部曲⼀样。后⾯慢慢⼤家就会体会到，动规五部曲⽅法的重要性。<br />动态规划<br />动规五部曲：<br />这⾥我们要⽤⼀个⼀维dp数组来保存递归的结果

解题思路五部曲

确定dp数组以及下标的含义
dp[i]的定义为：第i个数的斐波那契数值是dp[i]
确定递推公式
为什么这是⼀道⾮常简单的⼊⻔题⽬呢？
因为题⽬已经把递推公式直接给我们了：状态转移⽅程 dp[i] = dp[i - 1] + dp[i - 2];
dp数组如何初始化
题⽬中把如何初始化也直接给我们了，如下：
确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序
⼀定是从前到后遍历的
举例推导dp数组
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导⼀下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是⼀致的。以上我们⽤动规的⽅法分析完了，C++代码如下： ```c

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


时间复杂度：O(n) 空间复杂度：O(n)<br />当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列。    代码如下：
```c

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

时间复杂度：O(n) 空间复杂度：O(1)
递归解法
本题还可以使⽤递归解法来做代码如下：


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

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

二、爬楼梯

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

解题思路五部曲

1. 确定dp数组以及下标的含义
dp[i]：爬到第i层楼梯，有dp[i]种⽅法
2. 确定递推公式
如果可以推出dp[i]呢？
从dp[i]的定义可以看出，dp[i] 可以有两个⽅向推出来。
⾸先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种⽅法，那么再⼀步跳⼀个台阶不就是dp[i]了么。还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种⽅法，那么再⼀步跳两个台阶不就是dp[i]了么。那么dp[i]就是dp[i - 1]与dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] 。
在推导dp[i]的时候，⼀定要时刻想着dp[i]的定义，否则容易跑偏。这体现出确定dp数组以及下标的含义的重要性！
3. dp数组如何初始化
在回顾⼀下dp[i]的定义：爬到第i层楼梯，有dp[i]中⽅法。
那么i为0，dp[i]应该是多少呢，这个可以有很多解释，但都基本是直接奔着答案去解释的。
例如强⾏安慰⾃⼰爬到第0层，也有⼀种⽅法，什么都不做也就是⼀种⽅法即：dp[0] = 1，相当于直接站在楼顶。
但总有点牵强的成分。
那还这么理解呢：我就认为跑到第0层，⽅法就是0啊，⼀步只能⾛⼀个台阶或者两个台阶，然⽽楼层是
0，直接站楼顶上了，就是不⽤⽅法，dp[0]就应该是0.
其实这么争论下去没有意义，⼤部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过，然后就往结果上靠去解释dp[0] = 1。
从dp数组定义的⻆度上来说，dp[0] = 0 也能说得通。
需要注意的是：题⽬中说了n是⼀个正整数，题⽬根本就没说n有为0的情况。所以本题其实就不应该讨论dp[0]的初始化！
我相信dp[1] = 1，dp[2] = 2，这个初始化⼤家应该都没有争议的。
所以我的原则是：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
4. 确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序⼀定是从前向后遍历的
5. 举例推导dp数组
举例当n为5的时候，dp table（dp数组）应该是这样的

// 版本⼀
class Solution 
{ public:
    int climbStairs(int n) {
        if (n <= 1) return n; /* 因为下⾯直接对dp[2]操作了，防⽌空指针*/
        vector<int> dp(n + 1); dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { /*注意i是从3开始的*/
        dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

时间复杂度：O(n) 空间复杂度：O(n)
当然依然也可以，优化⼀下空间复杂度，代码如下：

// 版本⼆
class Solution 
{ public:
    int climbStairs(int n) { if (n <= 1) return n; int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { int sum = dp[1] + dp[2]; dp[1] = dp[2];
        dp[2] = sum;
        }
        return dp[2];
    }
};

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

三、最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：

cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据，范围为 [0, 999] 。
解题思路
1. 确定dp数组及其含义
dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。（注意这里认为是第一步一定是要花费）
2. 确定递推公式
有两个途径得到dp[i]：dp[i-1]和dp[i-2]
那选哪个呢？注意我们dp[i]的含义是花费的最少体力
因而 dp[i] = min(dp[i-1] , dp[i-2])+cost[i]

注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值
3. dp数组及其初始化
dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化
dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出

vector<int> dp(cost.size());
dp[0] = cost[0];
dp[1] = cost[1];

4. 确定遍历顺序
dp[i]是由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了
5. 举例推导dp数组
拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]，来模拟⼀下dp数组的状态变化

具体代码实现如下

Class solution
{ public:
    int minCostlimbingstairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < cost.size(); i++){
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
        }
        // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return min(dp[cost.size()-1], dp[cost.size()-2]);
    }
};

时间复杂度O(n)
空间复杂度O(n)
还可以优化时间复杂度

Class solution
{ public:
    int minCostlibingstairs()vector<int>& cost) {
        int dp0 = cost[0];
        int dp1 = cost[1];
        for(int i = 2; i < cost.size(); i++) {
            int dp2 = min(dp1, dp0) + cost[i];
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp2;
    }
};

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

四、不同路径问题

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：

输入：m = 3, n = 7 输出：28
示例 2：输入：m = 2, n = 3 输出：3 解释：从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

示例 3：输入：m = 7, n = 3 输出：28
示例 4：输入：m = 3, n = 3 输出：6
提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9
1、深度搜索
这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。
注意题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一颗二叉树，而叶子节点就是终点！
如图举例：

此时问题就可以转化为求二叉树叶子节点的个数，代码如下： ```c class Solution { private: int dfs(int i, int j, int m, int n) {
```
  if (i > m || j > n) return 0; // 越 界 了
  if (i == m && j == n) return 1; // 找到⼀种⽅法，相当于找到了叶⼦节点
  return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
```
} public: int uniquePaths(int m, int n) {
```
  return dfs(1, 1, m, n);
```
} };

**大家如果提交了代码就会发现超时了！**<br />来分析一下时间复杂度，这个深搜的算法，其实就是要遍历整个二叉树。<br />这颗树的深度其实就是m+n-1（深度按从1开始计算）。<br />那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）<br />所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1)，可以看出，这是指数级别的时间复杂度，是非常大的。
<a name="qxyLk"></a>
#### 2、动态规划
<a name="EoHyQ"></a>
#### 解题思路
机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。<br />按照动规五部曲来分析：

1. **确定dp数组(dp table)的含义**

dp[i][j]表示从（0，0）出发到（i，j）有多少条不同的路径

2. **确定递推公式**

想要求dp[i][j]，只能从两个方向推得 dp[i-1][j]和dp[i][j-1]<br />回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。<br />那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。

3. **dp数组的初始化**

显然从（0，0）到（i，0）以及（0，j）均只有一种路径<br />故：初始化如下
```c
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int j = 0; i < n; j++) dp[0][j] = 1;

确定遍历顺序

显然dp[i][j] = dp[i-1][j] + dp[i][j-1]；dp[i][j]由其上方和左方推导得来，那么从左到右，一层一层遍历即可。

举例推导dp数组

分析完毕

代码如下

Class Solution
{ public:
    int uniquePaths(int m, int n) {
        vector<vrctor<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++)    dp[i][0] = 1;
        for(int j = 0; j < n; j++)    dp[0][j] = 1;
        for(int 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];
    }
};

时间复杂度：O(mn)
空间复杂度：O(mn)
空间复杂度优化

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

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

3、数论

在这个图中，可以看出⼀共m，n的话，⽆论怎么⾛，⾛到终点都需要 m + n - 2 步。

在这m + n - 2 步中，⼀定有 m - 1 步是要向下⾛的，不⽤管什么时候向下⾛。
那么有⼏种⾛法呢？可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有⼏种取法。那么这就是⼀个组合问题了。

求组合的时候，要防⽌两个int相乘溢出！ 所以不能把算式的分⼦都算出来，分⺟都算出来再做除法。

代码如下

Class Solution 
{ public:
    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) 空间复杂度：O(1)

五、不同路径问题（带障碍）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

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

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 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数组及其下标含义

dp[i][j] : 表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

确定递推公式

但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。

if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}

dp数组的初始化

显然dp[i][0]，dp[0][j]都应该是1，（如果途中没有障碍的话）
因而代码

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

确定遍历顺序

显然从左至右，一层一层遍历

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        if (obstacleGrid[i][j] == 1) continue;
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
}

举例推导dp数组

拿示例1来举例如题：

对应的dp table 如图：

如果这个图看不同，建议在理解一下递归公式，然后照着文章中说的遍历顺序，自己推导一下！
动规五部分分析完毕，对应C++代码如下：

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

时间复杂度O(n * m) n m 分别为obstacleGrid 长度和宽度
空间复杂度O(n * m)
六、整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
示例 1: 输入: 2 输出: 1
\解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。
动规五部曲，分析如下：

确定dp数组（dp table）以及下标的含义

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
dp[i]的定义讲贯彻整个解题过程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！

确定递推公式

可以想 dp[i]最大乘积是怎么得到的呢？
其实可以从1遍历j，然后有两种渠道得到dp[i].
一个是j (i - j) 直接相乘。
一个是j dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。
那有同学问了，j怎么就不拆分呢？
j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。那么从1遍历j，比较(i - j) j和dp[i - j] j 取最大的。递推公式：
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
也可以这么理解，j (i - j) 是单纯的把整数拆分为两个数相乘，而j dp[i - j]是拆分成两个以及两个以上的个数相乘。
如果定义dp[i - j] dp[j] 也是默认将一个数强制拆成4份以及4份以上了。
**所以递推公式：dp[i] = max({dp[i], (i - j) j, dp[i - j] j});*
那么在取最大值的时候，为什么还要比较dp[i]呢？
因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。

dp的初始化

不少同学应该疑惑，dp[0] dp[1]应该初始化多少呢？
有的题解里会给出dp[0] = 1，dp[1] = 1的初始化，但解释比较牵强，主要还是因为这么初始化可以把题目过了。
严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。
拆分0和拆分1的最大乘积是多少？
这是无解的。
这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！

确定遍历顺序

确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) j, dp[i - j] j));
dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。
枚举j的时候，是从1开始的。i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。
所以遍历顺序为：

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j < i - 1; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

举例推导dp数组

举例当n为10 的时候，dp数组里的数值，如下：

代码如下

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

时间复杂度：O(n^2)
空间复杂度：O(n)
七、不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
来看看n为3的时候，有哪几种情况。
当1为头结点的时候，其右子树有两个节点，看这两个节点的布局，是不是和 n 为2的时候两棵树的布局是一样的啊！
（可能有同学问了，这布局不一样啊，节点数值都不一样。别忘了我们就是求不同树的数量，并不用把搜索树都列出来，所以不用关心其具体数值的差异）
当3为头结点的时候，其左子树有两个节点，看这两个节点的布局，是不是和n为2的时候两棵树的布局也是一样的啊！
当2位头结点的时候，其左右子树都只有一个节点，布局是不是和n为1的时候只有一棵树的布局也是一样的啊！
发现到这里，其实我们就找到的重叠子问题了，其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。
思考到这里，这道题目就有眉目了。
dp[3]，就是元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
动规五部曲

确定dp数组（dp table）以及下标的含义

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
也可以理解是i的不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。
以下分析如果想不清楚，就来回想一下dp[i]的定义

确定递推公式

在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] dp[以j为头结点右子树节点数量]
j相当于是头结点的元素，从1遍历到i为止。
所以递推公式：dp[i] += dp[j - 1] dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

dp数组如何初始化

初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。
那么dp[0]应该是多少呢？
从定义上来讲，空节点也是一颗二叉树，也是一颗二叉搜索树，这是可以说得通的。
从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1，否则乘法的结果就都变成0了。
所以初始化dp[0] = 1

确定遍历顺序

首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
那么遍历i里面每一个数作为头结点的状态，用j来遍历。
代码如下：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j];
    }
}

举例推导dp数组

n为5时候的dp数组状态如图：

当然如果自己画图举例的话，基本举例到n为3就可以了，n为4的时候，画图已经比较麻烦了。

C++代码如下：

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

八、买卖股票的最佳时机

给定一个数组 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
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/

惯例五部曲

动规五部曲

确定dp数组（dp table）以及下标的含义

dp[i][0] : 表示第 i 天持有股票所得的最多现金！【注意不一定是第 i 天买入，也可能是 i - 1 天就已经持有】
dp[i][1]: 表示第 i 天不持有股票所得的最多现金！【注意不一定是第 i 天卖出，也可能是 i - 1 天就已经卖出】

确定递推公式

如果第 i 天持有股票，即dp[i][0]：

第i-1天就持有，那么保持现状，所得现金就是前一天所持股票的所得。即 dp[i - 1][0]
第i天买入股票，所得现金就是买入今天的股票后所得的现金，即dp[i - 1][1] - prices[i]

那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
如果第i天不持有股票：

第i-1天就不持有股票，那么保持现状，所得现金就是前一天所持股票的所得。即 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数组如何初始化

由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])；可以看出
其基础都是从dp[0][0] 和 dp[0][1]推出
那么dp[0][0] 表示第 0 天持有此时持有的一定就是买入的了，即dp[0][0] = -prices[0]
dp[0][1] 表示第 0 天不持有股票，那就是0，所以dp[0][0] = 0。

确定遍历顺序

dp[i]都是由dp[i - 1]推导出来的，显然从前往后一次遍历即可。

举例推导dp数组

以示例2，输入【1，2，3，4，5】为例，dp数组状态如下

那么dp[4][1]就是最终结果，为啥不是dp[4][0]？因为不持有股票所得金钱一定比持有股票所得金钱多。
分析完毕

C++代码如下

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

时间复杂度 O（n）
空间复杂度 O（n）

可以看出dp[i]只是依赖dp[i - 1]的状态。
那么我们只需记录当前天和前一天的dp状态就可以了，可以使用滚动数组来节省空间，代码如下

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

时间复杂度 O（n）
空间复杂度 O（1）

思考这三个问题：

动态规划的解题步骤

一、斐波那契数，

解题思路五部曲

二、爬楼梯

解题思路五部曲

三、最小花费爬楼梯

解题思路

具体代码实现如下

四、不同路径问题

1、深度搜索

代码如下

3、数论

代码如下

五、不同路径问题（带障碍）

解题思路五部曲

六、整数拆分

动规五部曲，分析如下：

代码如下

七、不同的二叉搜索树

动规五部曲

C++代码如下：

八、买卖股票的最佳时机

惯例五部曲

动规五部曲

C++代码如下