什么问题可以用动态规划求解

你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。

计数

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

求最大最小值

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

求存在性

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

例题1 硬币组合问题

Lintcode 669

想法1 尽量用大的硬币
结果是：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代表什么
• 确定状态需要两个意识
  – 最后一步
  – 子问题

对于例题1，

• 虽然我们不知道最优策略是什么，但最优策略一定是K枚硬币a₁,a₂,…,a_k,加起来面值是27
• 一定有一枚最后的硬币：a_k
• 除掉这枚硬币，前面硬币的面值加起来是27 - a_k
• 

关键点1：我们不关心前面的k-1枚硬币是如何拼出27 - a_k 的（或有1种拼法或100种），而且甚至现在不知道 a_k 和k，但我们确定前面的硬币频出了27 - a_k 。

关键点2：因为是最优策略，所以拼出27 - a_k 的硬币数量一定要最少。

子问题

简介

• 所以我们就要求：最少用多少枚硬币可以拼出27 - a_k
• 原问题是最少用几枚硬币拼出27
• 我们将原问题转换成了一个子问题，而且规模更小：27 - a_k
• 为了简化定义，我们设状态 f ( x ) f(x) f(x) 表示：最少用几枚硬币拼出X

只要找到子问题，就可以用动态规划求解，如何确定状态十分重要

• 我们还不知道最后那枚 a_k 是多少？

• 最后那枚 a_k 只可能是2，5或者7

• 如果 a_k 是2， f ( 27 ) f(27) f(27)应该是 f ( 27 − 2 ) f(27-2) f(27−2) + 1 （加上最后这枚硬币2）

• 如果 a_k 是5， f ( 27 ) f(27) f(27)应该是 f ( 27 − 5 ) f(27-5) f(27−5) + 1 （加上最后这枚硬币5）

• 如果 a_k 是7， f ( 27 ) f(27) f(27)应该是 f ( 27 − 7 ) f(27-7) f(27−7) + 1 （加上最后这枚硬币7）

• 除此之外没有其他可能

• 新要求最少的硬币数，所以：
  f ( 27 ) = m i n ( f ( 27 − 2 ) + 1 , f ( 27 − 5 ) + 1 , f ( 27 − 7 ) + 1 ) f(27) = min(f(27-2)+1, f(27-5)+1, f(27-7)+1) f(27)=min(f(27−2)+1,f(27−5)+1,f(27−7)+1)

  递归解法

  

递归的问题

这样的递归会导致有些节点被重新计算，时间复杂度过高，如图中的红色节点

• 做了很多重复计算，效率低下
• 如何避免？
• 将计算结果保存下来，并且改变计算顺序

动态规划组成部分二：转移方程

• 设状态 f ( X ) f(X) f(X) 最少用多少枚硬币拼出x
• 对于任意X，有
  f ( X ) = m i n ( f ( X − 2 ) + 1 , f ( X − 5 ) + 1 , f ( X − 7 ) + 1 ) f(X) = min(f(X-2)+1,f(X-5)+1,f(X-7)+1) f(X)=min(f(X−2)+1,f(X−5)+1,f(X−7)+1)

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

• f ( 27 ) = m i n ( f ( 27 − 2 ) + 1 , f ( 27 − 5 ) + 1 , f ( 27 − 7 ) + 1 ) f(27) = min(f(27-2)+1, f(27-5)+1, f(27-7)+1) f(27)=min(f(27−2)+1,f(27−5)+1,f(27−7)+1)
• 两个问题：X - 2 和 X - 5 或者 X - 7 小于0怎么办？什么时候停下来？
• 如果不能拼出Y，就定义 f ( Y ) = f(Y) = f(Y)= + ∞ +\infty +∞ 表示失败
  – 比如 f ( − 1 ) = f ( − 2 ) = . . . = f(-1) = f(-2) = ... = f(−1)=f(−2)=...= + ∞ +\infty +∞
• 所以 f ( 1 ) = m i n ( f ( − 1 ) + 1 , f ( − 4 ) + 1 , f ( − 6 ) + 1 ) = f(1) = min(f(-1)+1, f(-4)+1, f(-6)+1)= f(1)=min(f(−1)+1,f(−4)+1,f(−6)+1)= + ∞ +\infty +∞
• 初始条件： f ( 0 ) = 0 f(0) = 0 f(0)=0
  初始条件是用转移方程算不出来，且需要手工定义的， f ( 0 ) f(0) f(0)不应该为 + ∞ +\infty +∞，这样才有 f ( 2 ) = 1 f(2) = 1 f(2)=1
  #动态规划组成部分四：计算顺序
• 拼出X所需要的最少硬币数： $f(X) = min(f(X-2)+1,f(X-5)+1,f(X-7)+1)$
• 初始条件： f ( 0 ) = 0 f(0) = 0 f(0)=0
• 然后计算 f ( 1 ) , f ( 2 ) , . . . , f ( 27 ) f(1),f(2),...,f(27) f(1),f(2),...,f(27)
• 当我们计算到 f ( X ) f(X) f(X)时， f ( X − 2 ) + 1 , f ( X − 5 ) + 1 , f ( X − 7 ) + 1 f(X-2)+1,f(X-5)+1,f(X-7)+1 f(X−2)+1,f(X−5)+1,f(X−7)+1都已经有结果了

小结

• 动态规划组成部分：
  -1. 确定状态

  • List item最后一步（最优策略中使用的最后一枚硬币）
  • 化成子问题（最少的硬币拼出更小的面值27- a_k)

  -2. 转移方程

  • f ( X ) = m i n ( f ( X − 2 ) + 1 , f ( X − 5 ) + 1 , f ( X − 7 ) + 1 ) f(X) = min(f(X-2)+1,f(X-5)+1,f(X-7)+1) f(X)=min(f(X−2)+1,f(X−5)+1,f(X−7)+1)

  -3.初始条件和边界情况

  • f ( 0 ) = 0 f(0) = 0 f(0)=0 ，如果不能拼出Y， f ( Y ) = f(Y) = f(Y)= + ∞ +\infty +∞

  -4.计算顺序

  • $f(0)，f(1) ，f(2) ，… $