动态规划

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

解题步骤：

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

509. 斐波那契数

link
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1， F(n) = F(n - 1) + F(n - 2)，其中 n > 1。给你 n ，请计算 F(n) 。

思路

确定 dp 数组（dp table）以及下标的含义：第 i 个数的斐波那契数值是 dp[i]
确定递推公式：题目中已经告知 dp[i] = dp[i - 1] + dp[i - 2]
dp 数组如何初始化：题目中也告知 dp[0] = 0, dp[1] = 1
确定遍历顺序：从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
举例推导 dp 数组：

class Solution:
    def fib(self, n: int) -> int:
        res = [0, 1]

        for i in range(2, n + 1):
            res.append(res[i - 1] + res[i - 2])
        
        return res[n]

70. 爬楼梯

link

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

思路

确定 dp 数组（dp table）以及下标的含义：到达第 i 阶的走法为 dp[i]
确定递推公式：可以定义为 dp[i] = dp[i - 1] + dp[i - 2]（dp[i - 1] 走一步，dp[i - 2] 走两步）
dp 数组如何初始化：第 0 阶不走，可以定义为 0（dp[0] = 0）,第一阶只有 1 种走法（dp[1] = 1），第二阶有 2 种（dp[2] = 2）
确定遍历顺序：从前往后
举例推导 dp 数组：

class Solution:
    def climbStairs(self, n: int) -> int:
        res = [0, 1, 2]

        for i in range(3, n + 1):
            res.append(res[i - 1] + res[i - 2])
        
        return res[n]

746. 使用最小花费爬楼梯

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

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

思路

确定 dp 数组（dp table）以及下标的含义：到达第 i 阶的最小花费
确定递推公式：可以定义为 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])（dp[i - 1] 走一步，dp[i - 2] 走两步）
dp 数组如何初始化：题目已经给出，可以从 0 或者 1 开始走，说明 dp[0] dp[1] 都是 0
确定遍历顺序：从前往后
举例推导 dp 数组：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        res = 0
        dp = [0, 0]
        for i in range(2, len(cost) + 1):
            dp.append(min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]))
        
        return dp[len(cost)]

62.不同路径

link

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

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

思路

确定 dp 数组（dp table）以及下标的含义：到达第 (i, j) 位置的方法数
确定递推公式：可以定义为 dp[i][j] = dp[i-1][j] + dp[i][j-1]，要么从左边来，要么从上面来。注意考虑边界情况
dp 数组如何初始化：可以定义为 1，这样 dp[0][1] 和 dp[1][0] 就可以使用递推公式来计算了
确定遍历顺序：从前往后
举例推导 dp 数组：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                # 第一行
                if i == 0:
                    if j != 0:
                        dp[i][j] = dp[i][j - 1]
                # 第一列
                elif j == 0:
                    if i != 0:
                        dp[i][j] = dp[i - 1][j]
                # 剩余情况
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        return dp[m - 1][n - 1]

其实第一行（dp[0][:]）和第一列（dp[:][0]）只能为 1，所以可以从 1 开始遍历

数论思路（高中数学 😂）

一共需要 m - 1 个竖着走和 n - 1 个横着走，总共是 m + n - 2 个步骤。相当于是给 m + n - 2 个不同的数，随便取 m - 1 个数，有几种取法。

63. 不同路径 II

link

给定一个 m x n 的整数数组 grid。一个机器人初始位于左上角（即 grid[0][0]）。机器人尝试移动到右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

思路

确定 dp 数组（dp table）以及下标的含义：到达 dp[i][j] 的路径数
确定递推公式：当前位置的路径数量等于左边和上面位置的路径数量 +1。前提是没有障碍物
dp 数组如何初始化：dp[0][0] 为 1
确定遍历顺序：从左上往右下
举例推导 dp 数组

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        n = len(obstacleGrid)
        m = len(obstacleGrid[0])
        dp = [[0] * m for _ in range(n)]
        dp[0][0] = 1
        for i in range(n):
            for j in range(m):
                if obstacleGrid[i][j] != 1:
                    if i == 0:
                        if j != 0:
                            dp[i][j] = dp[i][j - 1]
                    elif j == 0:
                        if i != 0:
                            dp[i][j] = dp[i - 1][j]
                    else:                        
                            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                else:
                    dp[i][j] = 0

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

要注意长和宽的定义，这里用第 N 个维度来理解：n 是维度 1，m 是维度 2。在初始化 dp 数组时需要先初始化维度 2（[0] * m）

空间优化版本

每次只能向右或下走，所以可以用一个一维数组来记录当前行第 j 列的 dp 值。可以理解为按照行来计算，先前的行计算好之后就不需要保存了。


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n, m = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * m  # 一维数组，dp[j]表示当前行第j列的路径数
        dp[0] = 0 if obstacleGrid[0][0] == 1 else 1  # 起点障碍则无路可走

        for i in range(n):
            for j in range(m):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0  # 当前格是障碍，路径数清零
                elif j > 0:
                    dp[j] += dp[j - 1]  # 左方 + 上方（上方就是dp[j]旧值）
        return dp[-1]

343. 整数拆分

link

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

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

思路

注意题目中的 k 没有指定，且 n >= 2。

确定 dp 数组（dp table）以及下标的含义：dp[i] 表示整数 i 拆分后得到的最大乘积
确定递推公式：遍历 [2, i}，假设变量为 j，则 i 拆分为了 j 和 i - j 两部分，有两种渠道得到 dp[i]：
- 一个是j * (i - j) 直接相乘。
- 一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。
- 注意这里不拆分 j！！
  - 当遍历到更小的 i 时（例如在计算 dp[j] 时），j 本身的最优拆法已经被计算过了。
  - 因此，如果“拆左边能更优”，这个结果早已体现在 dp[j] 自身中，并会在别的状态转移时被利用到。
  - 当 i 不断增大时，dp[j] 已经包含了“对 j 最优拆法”的结果，
dp 数组如何初始化：dp[2] == 1, dp[3] == 2
确定遍历顺序：从前往后遍历
举例推导 dp 数组：dp[4] = dp[3] * (4 - 3 + 1) = 4

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1
        
        for i in range(3, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        
        return dp[n]

96.不同的二叉搜索树

link

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

思路

回顾二叉搜索树：

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

思路：

确定 dp 数组（dp table）以及下标的含义：i 个元素可以组成 dp[i] 种二叉搜索树
确定递推公式：画几个图：
- 当 1 为头结点的时候，其右子树有两个节点，看这两个节点的布局，和 n 为 2 的时候两棵树的布局是一样的！
- 当 3 为头结点的时候，其左子树有两个节点，这两个节点的布局，和 n 为 2 的时候两棵树的布局也是一样的啊！
- 当 2 为头结点的时候，其左右子树都只有一个节点，布局是不是和n为1的时候只有一棵树的布局也是一样的啊！
- 总结一下：
  - 元素 1 为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有 0 个元素的搜索树数量
  - 元素 2 为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有 1 个元素的搜索树数量
  - 元素 3 为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有 2 个元素的搜索树数量
  - 而 dp[3] = 元素 1 为头结点搜索树的数量 + 元素 2 为头结点搜索树的数量 + 元素 3 为头结点搜索树的数量
dp 数组如何初始化：节点数为 0 时，空节点也是一棵二叉树，也是一棵二叉搜索树，所以 dp[0] == 1；此外，上面提到需要乘左子树有 0 个元素的搜索树数量，所以定义为 1
确定遍历顺序：从前往后
举例推导 dp 数组

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range (1, n + 1):
            for j in range(1, i + 1):

                dp[i] += dp[j - 1] * dp[i - j]
        
        return dp[n]