动态规划算法综述

动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。如何拆分问题,才是动态规划的核心。而拆分问题,靠的就是状态的定义状态转移方程的定义


动态规划题目特点

计数

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

求最大最小值

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

求存在性

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

动态规划组成部分一:确定状态

例题:你有三种硬币,分别面值2元、5元和7元,每种硬币都有足够多。买一本书需要27元,如果用最少的硬币组合正好付清,不需要对方找钱

  • 确定状态需要两个意识:

    • 最后一步 (最优策略中使用的最后一枚硬币ak)
    • 子问题 (最少的硬币拼出更小的面值27-ak)

最后一步

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

关键点1:我们不关心前面的k-1枚硬币是怎么拼出27-ak的(可能有1种拼法,可能有100种拼法),而且我们现在甚至还不知道ak和k,但是我们确定前面的硬币拼出来27-ak

关键点2:因为是最优策略,所以拼出27-ak的硬币一定要最少,否则这就不是最优策略了

子问题

  • 所以我们就要求:最少用多少枚硬币可以拼出27-ak
  • 原问题是最少用多少枚硬币拼出27
  • 我们将原问题转化成了一个子问题,而且规模更小:27-ak
  • 为了简化定义,我们设状态f(x)=最少用多少枚硬币拼出X
  • 最后那枚硬币ak只可能是2,5,或者7

    • 如果ak是2,f(27)应该是f(27-2)+1 <加上最后这枚硬币>
    • 如果ak是5,f(27)应该是f(27-5)+1 <加上最后这枚硬币>
    • 如果ak是7,f(27)应该是f(27-7)+1 <加上最后这枚硬币>
  • 需要求最少的硬币数,所以:f(27) = min{f(27-2)+1,f(27-5)+1,f(27-7)+1}

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

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

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

  • f[X] = min{f[27-2]+1,f[27-5]+1,f[27-7]+1}
  • 如果不能拼出Y,就定义f[Y] = 正无穷

    • 例如f[-1]=f[-2]=...=正无穷
  • 初始条件: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[27]
  • 当我们计算到f[X]时,f[X-2],f[X-5],f[X-7]都已经得到结果了
添加新评论