动态规划（Dynamic Programming）题目特点
1. 计数
- 有多少种方式走到右下角
- 有多少种方法选出k个数使得和是Sum
2. 求最大最小值
- 从左上角走到右下角路径的最大数字和
- 最长上升子序列长度
3. 求存在性
- 取石子游戏，先手是否必胜
- 能不能选出k个数使得和是Sum
例1：硬币组合——最大最小值动态规划
题目描述：
你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多
• 买一本书需要27元
• 如何用最少的硬币组合正好付清，不需要对方找钱。
直觉：
最少硬币组合 → 尽量用面值大的硬币
• 7+7+7 = 21
• 21 + 5 = 26
• 呃。。。
改进：
尽量用大的硬币，最后如果可以用一种硬币付清就行
• 7+7+7 = 21
• 21 + 2 + 2 + 2 = 27
• 6枚硬币，应该对了吧。。。
然而，正确答案：7 + 5 + 5 + 5 + 5 = 27，5枚硬币。
动态规划组成部分一：确定状态
状态在动态规划中的作用属于定海神针。简单的说，解动态规划的时候需要开一个数组，数组的每个元素 f[i] 或者 f[i][j] 代表什么，类似于解数学题中，X，Y，Z代表什么。确定状态需要两个意识：最后一步和子问题。
- 最后一步
虽然我们不知道最优策略是什么，但是最优策略肯定是 K 枚硬币 a1, a2,…, aK 面值加起来是27，所以一定有一枚最后的硬币 aK。除掉这枚硬币，前面硬币的面值加起来是27- aK。
我们不关心前面的K-1枚硬币是怎么拼出27- aK 的（可能有1种拼法，可能有 100种拼法），而且我们现在甚至还不知道 aK 和 K，但是我们确定前面的硬币拼出了 27- aK 。因为是最优策略，所以拼出27- aK 的硬币数一定要最少，否则这就不是最优策略了。
- 子问题
所以我们就要求：最少用多少枚硬币可以拼出27- aK。原问题是最少用多少枚硬币拼出27，我们将原问题转化成了一个子问题，而且规模更小：27- aK。为了简化定义，我们设状态 f(X) 等于最少用多少枚硬币拼出X。
等等，我们还不知道最后那枚硬币aK是多少。最后那枚硬币 aK 只可能是2，5或者7。如果 aK 是2，f(27)应该是f(27-2) + 1 (加上最后这一枚硬币2）；如果 aK 是5，f(27)应该是f(27-5) + 1 (加上最后这一枚硬币5）；如果 aK 是7，f(27)应该是f(27-7) + 1 (加上最后这一枚硬币7）。除此以外，没有其他的可能了 。
需要求最少的硬币数，所以： f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}
基于上述分析，可以使用递归的方式来解决：
def coin_change_re(x):
if x == 0:
return 0
res = 1e15
if x >= 2:
res = min(ch_coin_re(x-2)+1, res)
if x >= 5:
res = min(ch_coin_re(x-5)+1, res)
if x >= 7:
res = min(ch_coin_re(x-7)+1, res)
return res
但是有很多重复计算，效率低下。下图计算了三次f(20)：
解决方式：将计算结果保存下来，并改变计算顺序。
动态规划组成部分二：转移方程
设状态f[X]=最少用多少枚硬币拼出X 。
动态规划组成部分三：初始条件和边界情况
f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
两个问题：
X-2, X-5 或者X-7小于0怎么办？什么时候停下来？
如果不能拼出Y，就定义f[Y]=正无穷。例如f[-1]=f[-2]=…=正无穷
所以：
初始条件：f[0] = 0
f[1] =min{f[-1]+1, f[-4]+1,f[-6]+1}=正无穷, 表示拼不出来1
动态规划组成部分四：计算顺序
• 拼出X所需要的最少硬币数：f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
• 初始条件：f[0] = 0
• 然后计算f[1], f[2], …, f[27]
• 当我们计算到f[X]时，f[X-2], f[X-5], f[X-7]都已经得到结果了。
f[0] = 0
f[1] = min{f[-1]+1, f[-4]+1,f[-6]+1} = ∞
f[2] = min{f[0]+1, f[-3]+1,f[-5]+1} = 1
f[3] = min{f[1]+1, f[-2]+1,f[-4]+1} = ∞
f[4] = min{f[2]+1, f[-1]+1,f[-3]+1} = 2
f[5] = min{f[3]+1, f[0]+1,f[-2]+1} = 1
f[6] = min{f[4]+1, f[1]+1,f[-1]+1} = 3
……
f[27] = 5
每一步尝试三种硬币，一共27步。与递归算法相比，没有任何重复计算。算法时间复杂度（即需要进行的步数）： 面额数x硬币种类。这里是27x3。
代码如下：
def coin_change(coins, amount):
"""
换零钱动态规划算法
:param coins: 零钱种类整数列表
:param amount: 需要换的面值
:return: 最少换取的硬币数
"""
MAX_VALUE = 1e15
states = [MAX_VALUE] * (amount+1) # 状态数组初始化，包含状态0
states[0] = 0 # 初始值为0
for i in range(1, amount+1): # 依次求每个状态
for coin in coins: # 遍历所有硬币种类，求最小值
if i - coin < 0:
continue
states[i] = min(states[i], states[i-coin]+1)
if states[amount] == MAX_VALUE:
return -1
return states[amount]
小结
求最值型动态规划，动态规划组成部分：
- 确定状态
• 最后一步（最优策略中使用的最后一枚硬币aK）
• 化成子问题（最少的硬币拼出更小的面值27-aK） - 转移方程
• f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1} - 初始条件和边界情况
• f[0] = 0
• 如果不能拼出Y，f[Y]=正无穷 - 计算顺序
• f[0], f[1], f[2], …
例2：不同的路径数——计数型动态规划
题目描述：
给定m行n列的网格，有一个机器人从左上角(0,0)出发，每一步可以向下 或者向右走一步，问有多少种不同的方式走到右下角。
组成部分一：确定状态
最后一步：无论机器人用何种方式到达右下角，总有最后挪动的一步：向右或者向下。右下角坐标设为(m-1, n-1) ，那么前一步机器人一定是在(m-2, n-1)或者(m-1, n-2) 。
子问题：如果机器人有X种方式从左上角走到(m-2,n-1)，有Y种方式从左上 角走到(m-1,n-2)，则机器人有X+Y种方式走到(m-1, n-1)。问题转化为，机器人有多少种方式从左上角走到(m-2, n-1)和(m-1, n-2)。原题要求有多少种方式从左上角走到(m-1, n-1)。
状态：设 f[i][j] 为机器人有多少种方式从左上角走到(i, j)。
组成部分二：转移方程
组成部分三：初始条件和边界情况
- 初始条件：f[0][0] = 1，因为机器人只有一种方式到左上角（什么都不做）
- 边界情况：i = 0 或 j = 0，则前一步只能有一个方向过来。
组成部分四：计算顺序
- f[0][0] = 1
- 计算第0行：f[0][0], f[0][1], …, f[0][n-1]
- 计算第1行：f[1][0], f[1][1], …, f[1][n-1]
… - 计算第m-1行：f[m-1][0], f[m-1][1], …, f[m-1][n-1]
- 答案是f[m-1][n-1]
- 时间复杂度（计算步数）：O(MN)，空间复杂度（数组大小）：O(MN)
代码如下：
def unique_paths(m, n):
"""
:param m: 网格行数
:param n: 网格列数
:return: 从左上角到右下角所有的路径数
"""
states = [[0] * n] * m # 状态数组
states[0][0] = 1
for i in range(m):
for j in range(n):
if i == 0 or j == 0: # 边界处都只有一条路可走
states[i][j] = 1
else:
states[i][j] = states[i - 1][j] + states[i][j-1]
return states[m-1][n-1]
例3：跳跃游戏——存在型动态规划
题目描述：
有n块石头分别在x轴的0, 1, …, n-1位置，一只青蛙在石头0，想跳到石头n-1。如果青蛙在第 i 块石头上，它最多可以向右跳距离ai 。问青蛙能否跳到石头n-1？
例子：
输入：a=[2, 3, 1, 1, 4] 输出：True
输入：a=[3, 2, 1, 0, 4] 输出：False
组成部分一：确定状态
- 最后一步：如果青蛙能跳到最后一块石头n-1，我们考虑它跳的最后一步，这一步是从石头i跳过来，i<n-1。这需要两个条件同时满足：青蛙可以跳到石头i；最后一步不超过跳跃的最大距离：n-1-i<=ai 。
- 子问题：那么，我们需要知道青蛙能不能跳到石头i (i<n-1)，而我们原来要求青蛙能不能跳到石头n-1。
- 状态：设 f[j] 表示青蛙能不能跳到石头 j 。
组成部分二：转移方程
组成部分三：初始条件和边界情况
初始条件：f[0] = True，因为青蛙一开始就在石头0。
组成部分四：计算顺序
• 设f[j]表示青蛙能不能跳到石头j
•
• 初始化 f[0]=True
• 计算 f[1], f[2], …, f[n-1]
• 答案是 f[n-1]
• 时间复杂度：O(N2)，空间复杂度（数组大小）：O(N)
代码如下：
def jump_game(n, lst):
states = [False] * n
states[0] = True
for i in range(1, n):
for j in range(i):
if states[j] and lst[j] + j >= i:
states[i] = True
break
return states[n-1]
以上代码时间复杂度为 O(N2)，一般会运行超时，但是也是需要掌握的。优化后的代码（时间复杂度O(N)）：
def jump_game(n, lst):
max_reach = 0
for i, x in enumerate(lst):
if max_reach < i: return False # 如果之前的最远距离下标，小于当前的下标，就gg
if max_reach >= n - 1: return True # 或者大于最远直接返回True
max_reach = max(max_reach, i + x) # 每一步更新可以跳到的最远距离下标
总结
四个组成部分：
- 确定状态
• 研究最优策略的最后一步
• 化为子问题 - 转移方程
• 根据子问题定义直接得到 - 初始条件和边界情况
• 细心，考虑周全 - 计算顺序
• 利用之前的计算结果
常见动态规划类型：
- 坐标型动态规划 (20%)
- 序列型动态规划 (20%)
- 划分型动态规划 (20%)
- 区间型动态规划 (15%)
- 背包型动态规划 (10%)
- 拓扑型动态规划 (5%)
- 博弈型动态规划 (5%)
- 综合性动态规划 (5%)
