动态规划1——入门

动态规划（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]

小结

求最值型动态规划，动态规划组成部分：

1. 确定状态
   • 最后一步（最优策略中使用的最后一枚硬币aK）
   • 化成子问题（最少的硬币拼出更小的面值27-aK）
2. 转移方程
   • f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
3. 初始条件和边界情况
   • f[0] = 0
   • 如果不能拼出Y，f[Y]=正无穷
4. 计算顺序
   • 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(N²)，空间复杂度（数组大小）：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(N²)，一般会运行超时，但是也是需要掌握的。优化后的代码（时间复杂度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%)