leetcode_动态规划入门

3 minutes read
进阶之路
面试 • 算法

动态规划一般出现在难度中上的题目中，一直以来都是比较束手无策的！

抽空看了一章“九章算法”的【动态规划专题班】动态规划入门 Introduction to Dynamic Programming，讲的挺好的。下面是笔记

消除恐惧的最好办法就是面对恐惧！

题目特点

  1. 计数

    • 有多少种方式走到右下角
    • 有多少种方法选出k个数使得和为sum

  2. 求最大最小值

    • 左上角到右下角路径的最大数字和
    • 最长上升子序列长度

  3. 求存在性

    • 取石子游戏，先手是否必胜
    • 能不能选出k个数使得和为sum

例题1：Coin Change

题目

  • 拥有硬币三种：2元、5元、7元，每种硬币足够多
  • 买一本书要27元
  • 如何用最少的硬币组合正好付清，不需要双方找钱

分析

最少硬币组合->动态规划

  1. 思路1: 尽量用最大的硬币

    • 7 + 7 + 7 = 21
    • 21 + 5 = 26
    • 找不清了

  2. 思路2：尽量用大的，最后如果能付清就行

    • 7 + 7 + 7 = 21
    • 21 + 2 + 2 + 2 = 27
    • 结果是6枚硬币
    • 然而正确结果为：7 + 5 + 5 + 5 + 5 = 27 五枚

解题流程

一、确定状态

  • 状态相当于定海神针
  • 简单来说，解动态规划需要开一个数组，数组的每个元素f[i]和f[i][j]代表什么
    • 类型于解数学题中 X、Y、Z代表什么
  • 确定状态需要有两个意识
    • 最后一步
    • 字问题
最后一步

虽然最优策略未知，但是结果肯定知道：K枚硬币 a1, a2, …, ak 面值加起来是 27

  • 所以一定有一枚 最后的 硬币：ak

  • 除掉这枚硬币，前面硬币面值加起来是 27-ak

        27 - ak     ak
|______________|_|
        |	    |
     k-1枚   最后一枚
    • 关键点1：我们不关心前面 k-1 是如何拼出结果 27-ak 的，可以确定的是拼出的结果为 27-ak
    • 关键点2：目标为最优策略，拼出的27-ak 所需硬币数一定要 最少
    • eg：22 + 5 = 27， 至少用四枚才能拼出22元（最后一枚去掉，对于22元来说，四枚还是最优的）
子问题
  • 需求转化为：最少用多少枚硬币可以拼出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}$

  • f(27) 为拼出27所需最小硬币数
  • min{} 求最小
    • 拼25所需最小硬币数 + 最后一枚 2
    • 拼22所需最小硬币数 + 最后一枚 5
    • 拼20所需最小硬币数 + 最后一枚 7

递归解法

func min(x, y int) int {
    if x > y {
        return y
    } 
    return x
}

// f(x) 最少使用多少枚拼出 x
func f(x int) int {
    // 0元用0枚
	if x == 0 {
		return 0
	}
    
    res = math.MaxInt32 // 假设有无穷多种，找到解就更新这个值
    if x >= 2 {
        res = min(f(x-2)+1, res)
    }
    if x >= 5 {
        res = min(f(x-5)+1, res)
    }
    if x >= 7 {
        res = min(f(x-7)+1, res)
    }
    return res
}

执行图

树中出现了较多重复运算，比如 f(20)，f(15)，指数级别的复杂度

如何避免？

动态规划：计算结果保存下来，并改变计算顺序

二、转移方程

设 f[27]=最少用多少枚硬币拼出X

对任意X：f[27] = min{f[27-2]+1，f[27-5]+1，f[27-7]+1}

  • f(27) 为拼出27所需最小硬币数
  • min{} 求最小
    • 拼25所需最小硬币数 + 最后一枚 2
    • 拼22所需最小硬币数 + 最后一枚 5
    • 拼20所需最小硬币数 + 最后一枚 7

三、初始条件和边界情况

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] = [-2] = 正无穷

  • 所以 f[1] = min{f[-1]+1, f[-4]+1, f[-6]+1} = 正无穷，表示拼不出来1

初始条件

转义方程算不出来的时候，需要手工定义

这里f[0] 如果要计算的话，得用到 f[-2]、f[-5]、f[-7]，显然不可能结果为正无穷

所以这里手动定义 f[0] = 0

边界情况

不要让数组越界

四、计算顺序

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]）

复杂度分析

每一步尝试3种硬币，一共27步

于递归相比，没有任何重复计算

时间复杂度（即需要进行的步数）：27 * 3 （O(m*n)，m种硬币拼成n块钱）

小结

  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], …
    • 原则：右边当前要用到的状态要先于左边的f计算出来

​

Coin Change解答

func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}

// coin:{2,5,7} |target:27 
func coinChange(A []int, m int) {
    // 创建一个dp，f[i]表示钱数为i时最少硬币数
	f := make([]int, m+1)
	// 初始状态 f[0] = 0，Golang不需要定义，默认为0
    
    // 从1块钱到27块开始凑
    for i := 0; i <= m; i++ {
        // 假设硬币为i时需要无穷多的硬币（找到最优解后回替换）
        f[i] = math.MaxInt32
        
        // 从硬币的可能情况里面找
        for j := range A {
            // 考虑边界值
            if i >= A[j] && f[i-A[j]] != math.MaxInt {
                // 留下较小的
            	f[i] = min(f[i-A[j]]+1, f[i])
            }
        }
    }
    if f[m] == math.MaxInt32 {
        return -1
    }
    return f[m]
}

分享：