动态规划（DP, Dynamic Programming）由于需要对问题进行抽象拆分，然后化简，因此具有一定的难度和乐趣。它属于一种算法设计的技巧，即对暴力遍历中的各种情况（重叠子问题）进行合理地剪枝，从而达到减小时间复杂度的目标。
动态规划的一般流程为：递归的暴力解法 → 带备忘录的递归解法 → 非递归的动态规划解法。也就是说，平时使用动态规划的方法来解决一个特定的问题时，并不是一蹴而就的，而是从暴力的问题出发进行一步步优化而来的。
此外，本文除了会对动态规划及其相关的应用进行阐述之外，还会介绍对动态规划问题进行优化的二分搜索法。
一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的。
缓存、重叠子问题、记忆化
以 Fibonacci 数列为例，直接写出来的代码是这样的：
def fib(n:int) -> int:
if n == 0:
return 0
elif n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
这是使用了递归的 Fibonacci 数列求解算法。因为是递归，所以该解法中一定会存在着重复部分，计算机还是会傻傻地对其重新计算一次，这便是需要进行优化剪枝的重叠子问题。我们可以在计算 fib(n) 之后，使用 LRU Cache 或者创建一个列表来把 fib(n) 给缓存起来，这样就可以避免对其进行重复运算，从而节省时间。
这便是动态规划最基本的运用，即通过一张表作为“备忘录”，从而减少递归的次数。
原本暴力求解的时间复杂度为 $O(n^2)$，经过优化后的时间复杂度仅为 $O(n)$。但是空间复杂度增大为了 $O(n)$，这本质上就是一个空间换时间的过程。
举个例子
下面用几个例子来归纳动态规划的原理：
凑零钱问题：「322.零钱兑换」
这一题其实可以通过递归的方法来解决，但是自从 LeetCode 改了测试集之后，递归解法就一定会超时（无论如何神优化都会超），所以只得从 DP 来入手。此题和背包问题一致，即求在固定的容量下能够装得下的最小（最大）数量。方法在于通过一个 DP Table 的形式来对最小硬币数量来进行记录，首先需要分析它的转移方程，当容量为 1（amount == 1）时的最优值一致往下推，等于 2 等于 3 等于 4……，最后等于 amount 的时候便可以得出最终的结果了。
代码如下：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float("inf")] * (amount + 1) # 初始的 DP Table
dp[0] = 0
for i in range(1, amount + 1): # 从 1 到 amount 递推
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]: # 如果 coin 满足要求，则进行兑换；< dp[i] 是因为要求最小值，小则进行替换
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != float("inf") else -1
最长递增子序列（LIS, Longest Increasing Subsequence）问题：「300. 最长递增子序列」
从动态规划的角度出发，首先对该问题进行化简；当前点与前面的点所组成的数组所对应的最长递增子序列，取决于前面的数字中能够与该点一起形成最长子序列的最大长度。所以可以得出状态转移方程（文字叙述）：每一个点对应的最长递增子序列的长度 = max(前面比该点小的点对应的最长递增子序列的长度) + 1，之所以要取 max() 是因为要求最长的子序列，然后新开辟一个数组空间（设为 temp）用来记录当前点与前面的数字组成的数列所对应的最长子序列即可。
代码如下：
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
length = len(nums)
dp = [1] * length # DP Table
for i in range(length):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) # 返回最长的的子序列长度
其实这样还是不够快，因为从代码的结构中可以看出，两层 for 里面没有任何剪枝条件，时间基本上会顶满 $O(n^2)$。
当然，对于这种情况还有优化的算法，便是二分搜索法（时间复杂度为 $O(n\log_2n)$）。这种方法属于不做一次根本想不到的方法，并且结果——为什么输出这个就是答案了——也涉及一定的数学证明，需要一定时间推敲。本文不会涉及相关内容，只是简单对该算法进行介绍作为拓展，平时使用动态规划进行解题足够。
代码如下：
class Solution:
def lengthOfLIS(self, nums: [int]) -> int:
tails, res = [0] * len(nums), 0 # base case
for num in nums:
i, j = 0, res
while i < j: # 二分查找
m = (i + j) // 2
if tails[m] < num: i = m + 1 # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
else: j = m
tails[i] = num
if j == res: res += 1
return res
LeetCode 用了一些比较阴间的样例来测试，所以直接使用动态规划算法的时间（3600+ ms）会明显长于二分查找法 + 动态规划的时间（60+ ms）。
「354. 俄罗斯套娃信封问题」
这一道问题看起来有些复杂，其实可以对信件的宽先进行排序，排序之后就会发现其实就是对高求解最长递增子序列（LIS, Longest Increasing Subsequence）问题。
纯动态规划的代码如下：
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
n = len(envelopes)
envelopes.sort(key=lambda x:(x[0], -x[1])) # 注意这里，第一个元素升序排列，第二个元素降序排列
dp = [1] * n
for i in range(1, n): # 对第二个元素进行 LIS 求解
for j in range(i):
if envelopes[i][1] > envelopes[j][1]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
名字是套娃问题，实际上也就是套娃问题，只需要注意同宽的情况下降序排列即可（注释处）。
第二个方法是二分查找法 + 动态规划，代码如下：
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
n = len(envelopes)
envelopes.sort(key=lambda x:(x[0], -x[1]))
arr=[envelopes[0][1]]
def bin_search(target):
l, r = 0, len(arr) - 1
while l <= r:
mid = l + (r - l) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
l = mid + 1
else:
r = mid - 1
return l
for i in range(1, n):
w, h = envelopes[i]
index = bin_search(h)
if index == len(arr):
arr.append(h)
else:
arr[index] = h
return len(arr)
同样，这一道题 LeetCode 也放了对纯 DP 不友好的阴间样例，所以只使用 DP 的话会比 DP + 二分查找优化要慢很多。