痛定思痛学DP，动态规划的一般性应用流程的总结

Dynamic Programming

动态规划

DP问题

【动态规划专题班】ACM总冠军、清华+斯坦福大神带你入门动态规划算法

目的：空间换时间，提升效率

方式：找出有规律性的递推公式以及限定条件

动态规划关键词

• 每一步最优
• 将问题划分为重复的子问题【到n-1步为整体 + 接下来的后一步】
  • 所以每次问题的形式是一致的，只是具体数据不同
  • $f_n=f_{n-1}+第n步$
  • $f_{i,j}...$
• 把问题以归纳方式从最基础范围开始递进
  • 因为第n步的结果就是前n-1步得到的最优结果加上第n步的结果，取最优得到
  • 因此避免重复计算，需要记录每步的结果

何时使用动态规划

问结果但不是具体内容的，求的是具体一个数，一般用DP比如

• 计数问题
  • 多少种路径
  • 多少种方法
• 求最大最小值
  • 子序列长度（最长、最短）
  • 数字和
• 求存在性
  • 先手是否取胜
  • 能不能选k个数使和最大

问所有种类的结果的内容，一般递归，深度搜索这些。

而，递归做了很多重复计算，因此可以将计算结果保存下来，避免重复计算。

动态问题的一般性处理步骤

一、确定状态

也就是$f_n,f_{i,j}$之类的

把问题分割为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\} fX​=min{fX−2​+1,fX−5​+1,fX−7​+1}

这里表达了$f_x$（最后一步）和$f_{X-}$（子问题）的关系

三、初始条件和边界情况

初始条件：

最开始(小范围)的数值，用于初始化，人工设定

（这些初始值用转移方程是算不出来的，然后后面递进计算又要用到的值）

比如:

• 一维情况下，$f_0,f_1$
• 二维情况下，$f_{0,0},f_{0,1},f_{1,0}$

这个维数和遍历对应，也和需要的变量对应

边界条件：

对于每次迭代计算，都要在合理的边界下计算

比如不存在的情况下，返回null

四、计算顺序

从前往后、从小往大、从大到小等。。。

顺序原则：看计算要依赖的方向，也就是转移方程中，谁靠谁得到后续的结果

demo1 青蛙跳石头

问题：在学习视频，1:10:52的地方

• 有n块石头分别在x轴的0，1，… n-1位置·一只青蛙在石头0，想跳到石头n-1
• 如果青蛙在第i块石头上，它最多可以向右跳距离$a_i$;
• 问青蛙能否跳到石头n-1
• 例子∶
  • 输入:a=[2, 3, 1, 1, 4]
  • 输出:True
  • 输入:a=[3, 2, 1, 0, 4]
  • 输出:False

思路（按照方法先自己想的）：

• 一、确定状态，分离子问题和最后一步

  蛙能否跳到n-1，能否跳到n-2，…，能否跳到1。

• 二、确定转移方程

  $f_n=(f_0+res{t}_0)||(f_1+res{t}_1)||...||(f_{n-1}+res{t}_{n-1})||(f_n+res{t}_n)$

  $res{t}_i$表示在石头$n_i$处剩下需要跳的数，跳过了，就$true$了

  有一个$true$就返回$true$

• 三、确定边界和初始值

  就n块石头

  $f_0=true$

• 四、整体总结

  需要一个一维变量boolean [n] re，记录是否可以跳到对应下标的石头上

  所以，数组re应该初始化为false,能跳再改为true

• 五、代码（没验证，凭感觉走的）

public boolean jump(int[] stone){
    // stone数组就是题目示例的数组a
    //定义数组re存结果
    n = stone.length;
    int[] re = new int[n];
    re[0] = true; //初始化
    
    for(int i = 0; i < n; i++){
        //得到在每块石头上的结果
        for(int j = 0; j < stone[i]; j++){
            if(re[j]){//代表可以跳到这块石头上
                re[i+j] = true; //把能跳的地方
            }
        }
    }
    return re[n-1];
}