动态规划的题目特点

1、记数

  • 有多少种方式走到右下角
  • 有多少种方法选出k个数使得和是sum
    2、求最大最小值
  • 从左上角走到右下角路径的最大数字和
  • 最长上升子序列长度
    3、求存在性
  • 取石子游戏，先手是否必胜
  • 能不能选出k个数使得和是sum

LintCode 669: Coin Change

1
2
3
4
5
- 你有三种硬币，分别面值是2元、5元、7原，每种硬币足够做
- 买一本书，需要27问
- 如何用最少得硬币组合正好付清27元，不需要对方付钱

 求最大最小值动态规划！

动态规划的组成部分之一： 确定状态

  • 状态在动态规划中的作用是定海神针
  • 简单的说，解动态对话的时候，需要开一个数组，数组的每个元素f(i)或者f(i)(j)代表什么
    • 类似于解数学题中的，xyz代表什么？
  • 确定状态需要两个意识
    • 最后一步
    • 子问题

最后一步是什么？

  • 虽然我们不知道最优策略是什么， 但是最优策略肯定是K枚硬币a1,a2…ak面值加起来是27
  • 所以一定有最后的硬币ak
  • 除掉这枚硬币，前面的硬币面值加起来是27-ak

子问题是什么？

  • 所以我们就要求： 最少用多少枚硬币可以拼出27-ak
  • 原问题是最少用多少枚硬币可以拼出27
  • 我们将原问题转换成一个子问题，而且规模变小了：17-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(x)=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}

递归解法： 效率比较低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def f(x):  # 最少用多少枚硬币，拼出x
    if x == 0:  # x=0 
        return 0
    res = float('inf')  # 无穷大
    if x >= 2:
        res = min(f(x - 2) + 1, res)  # 最后一枚是2  A
    if x >= 5:
        res = min(f(x - 5) + 1, res)  # 最后一枚是5
    if x >= 7:
        res = min(f(x - 7) + 1, res)  # 最后一枚是7
    return res


if __name__ == '__main__':
    print(f(5))
  • 递归做了很对的重复计算，效率低下
  • 如何避免？
  • 将计算结果保存下来，并改变计算顺序

动态规划的组成部分之一： 状态方程

  • 设状态f[x]=最少用多少枚硬币拼出X
  • 对任意的X，f[x]=min{f[27-2]+1,f[27-5]+1,f[27-7]+1} 40%

动态规划的组成部分之一： 初始条件和边界情况

  • f[x]=min{f[27-2]+1,f[27-5]+1,f[27-7]+1}

  • 两个问题： X-2，X-5或者X-7小于0 怎么办，什么时候停下来？

  • 如果不能拼出来Y，定义f(Y)为正无穷

  • 初始条件： f(0)=0

动态规划的组成部分之一： 计算顺序

  • 拼出x所需要的最小硬币数,f[x]=min{f[27-2]+1,f[27-5]+1,f[27-7]+1}
  • 初始条件： f[0] = 0
  • 计算f[1],f[2],f[3]…f[27]

小结：

动态规划组成部分:

  • 1、确定状态
    • 最后一步（最优策略中使用的最后一枚硬币ak）
    • 化成子问题（最少得硬币拼出更小的面值27-ak）
  • 2、转移方程
    • f[x]=min{f[27-2]+1,f[27-5]+1,f[27-7]+1}
  • 3、初始条件和边界情况
    • f[0] =0, 如果不能拼出Y，f[Y]=正无穷
  • 4、计算顺序
    • f[0],f[1]…

消除冗余，加速计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# A: { 2,5,7 }    M: 目标数27
def coinChange(A, M):  # 最少用多少枚硬币，拼出x
    f = [0 for  i in range(0,M+1)]
    n = len(A)

    f[0] = 0

    # f[1],f[2]...f[27]
    for i in range(1, M):
        f[i] = float("inf") # 假设无穷大
        # last coin A[0]、A[1]...A[n-1]
        # f[i]= min{f[27-A[0]]+1,f[27-A[1]]+1....f[27-A[n-1]]+1}
        for j in range(n): #  27*3
            if i >= A[j] and f[i - A[j]] != float("inf"):
                f[i] = min(f[i], f[i - A[j]] + 1)
    if f[M] == float("inf"):
        f[M] = -1
    return f[M]

OrderDict

__END__