PS. 本文是参考代码随想录做的一些笔记，完整版本请戳链接，非常好的教程！
如果某一问题有很多重叠子问题，使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优。
例如：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。贪心是每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
动态规划的解题步骤：
\quad
\quad
下面来做一些基础的题目~
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
给定 n ，请计算 F(n) 。
方法一：简单递归
class Solution:
def fib(self, n: int) -> int:
if n < 2: return n
return self.fib(n - 1) + self.fib(n - 2)
方法二：DP
class Solution:
def fib(self, n: int) -> int:
if n < 2: return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
这道题很简单，没啥可说的，可以看到DP方法花费的时间更少。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
这道题其实就是斐波那契数列！！
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。所以到第三层楼梯的状态可以由第二层楼梯和到第一层楼梯状态推导出来，那么就可以想到动态规划了。
确定dp数组以及下标的含义：dp[i]：爬到第i层楼梯，有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]。
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例1中只花费一个15 就可以到阶梯顶，最后一步可以理解为不用花费，这点很重要。
dp[i]的定义：
i个台阶所花费的最少体力为dp[i]。
递推公式：
dp[i]，一个是dp[i-1] 一个是dp[i-2]。一定是选花费最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]。（题目中的每当你爬上一个阶梯你都要花费对应的体力值，所以这里是cost[i]）class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0] * len(cost)
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, len(cost)):
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
return min(dp[len(cost) - 1], dp[len(cost) - 2])
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
dp[i][j]定义：表示从(0, 0)出发，到(i, j) 有dp[i][j]条不同的路径。
递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
事实上，dp数组使用一个一维数组就可以解决问题了，可以优化点空间。怎么理解呢？可以看下图：
从上图中可以发现，按行看，每次循环更新dp数组时都是在上一行的基础上更新的，也就是说每次前一行其实都被覆盖了。所以用一个一维数组就可以解决问题了。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1 for _ in range(n)]
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]
方法三：数论方法
一共 m m m行， n n n列的话，可以看到，从起点到终点，至少需要走 m + n − 2 m+n-2 m+n−2步。在这 m + n − 2 m + n - 2 m+n−2步中，一定有 m − 1 m - 1 m−1 步是要向下走的，不用管什么时候向下走。那么有几种走法呢？ 可以转化为，有 m + n − 2 m + n - 2 m+n−2个不同的数，随便取 m − 1 m - 1 m−1个数，有几种取法。这不就是一个组合问题吗？也就是一共有 C m + n − 2 m − 1 C_{m+n-2}^{m-1} Cm+n−2m−1种方法，计算公式知道吧？直接开写！
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
numerator = 1 # 分子
denominator = 1 # 分母
count = m - 1
t = m + n - 2
# 计算分子
while count:
count -= 1
numerator *= t
t -= 1
# 计算分母
for i in range(1, m):
denominator *= i
return int(numerator / denominator)
Python不用考虑溢出的问题，所以比较简单，直接照着公式算就行了。
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。
dp[i][j]的定义：表示从(0, 0)出发，到(i, j)有dp[i][j]条不同的路径。
递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
注意：(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
# 初始化第一列
for i in range(m):
if obstacleGrid[i][0] == 1: break
dp[i][0] = 1
# 初始化第一行
for j in range(n):
if obstacleGrid[0][j] == 1: break
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
- 时间复杂度：O(n × m)，n、m 分别为obstacleGrid 长度和宽度
- 空间复杂度：O(n × m)
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
递推公式：从1遍历j，然后有两种渠道得到dp[i]：
j * (i - j) 直接相乘。j * dp[i - j]，相当于是拆分(i - 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))。
注意：从dp[i]的定义来说，dp[0]和dp[1]就不应该初始化，也就是没有意义的数值。
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
dp[2] = 1
for i in range(3, n + 1):
for j in range(1, i - 1):
dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j)))
return dp[n]
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
**dp[i]**定义：1到**i**为节点组成的二叉搜索树的个数为**dp[i]**。
递推公式就有点复杂了，下面来具体看看：
对于
n
=
1
n=1
n=1的情况：
很明显，只有一种情况。
对于
n
=
2
n=2
n=2的情况：
这也很明显，只有两种情况。我们可以根据头节点拆分成两种情况：
为啥要这样看？这是为了和后面的情况进行推导。（很难想！）
对于
n
=
3
n=3
n=3的情况：
这个不是很好看，我们根据头节点拆分成三种情况：
也就是说，我们可以得到如下结论：
此外，我们可以知道：
dp[2]。dp[1]。dp[0]。回顾一下dp数组的定义，dp[3]就是元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量。即：
dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
根据这样的想法，我们可以推导初如下递推公式：dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]。j相当于是头结点的元素，从1遍历到i为止。所以递推公式：dp[i] += dp[j - 1] * dp[i - j]，j-1为j为头结点左子树节点数量，i-j为以j为头结点右子树节点数量。
从递推公式可以看出，推导的基础是dp[0]。所以只需要初始化dp[0]即可。空节点也是一颗二叉搜索树，所以初始化dp[0]=1没毛病！
从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
代码实现：
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]
\quad
\quad
\quad
\quad
持续更新中…