动态规划

动态规划(dynamic programming)：它是把研究的问题分成若干个阶段，且在每一个阶段都要“动态地”做出决策，从而使整个阶段都要取得最优效果。

理解：其实，无非就是利用历史记录，来避免我们的重复计算。
而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者多维数组来保存。

其实我挺好奇为什么用动态规划这个名字的，所以我花时间找了一下，如果大家想要知道这个名字的由来，可以去看看：动态规划

301

总结版解释：

适用场景

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划四步走

动态规划四步走：

301

明确数组的含义：

301

制作历史记录表：根据数组建表，填入初始值，利用递推关系式写程序推出其他空表项。

注意：这个是为我们通过初始值和递推关系式写出程序提供可视化条件以及思路，把抽象的东西可视化了，时时刻刻都知道自己要干嘛。
当然，如果脑子里有思路可以忽略。。

启发：这个想法其实是由编译原理中的 “编译程序绝大多数时间花在管理表格上” 这句话来的。
因为在编译中，编译的每个阶段所需要的信息多数从表格中读取，产生的中间结果都记录在相应的表格中，可以说整个编译过程就是造表、查表的过程。
也就是说，我们的动态规划算法也可以理解成造表、查表的一个过程。

301

寻找初始值出口：寻找数组元素初始值的出口，这个出口最好写在最前面，方便在一开始就出去，效率高；

注意：这个初始值要特别的给出一个出口，因为它们不是被递推出来的。

301

找出递推关系式：找出数组元素递推关系式。

注意：可以从 dp[i] = ? 这一数学公式开始推想。

明确数组的含义

第一步：定义数组元素的含义。
上面说了，我们会用一个数组，来保存历史记录，假设用一维数组 dp[]吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，即你的 dp[i] 是代表什么意思？

那么下面我来举个例子吧！
问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

首先，拿到这个题，我们需要判断用什么方法，要跳上n级的台阶，我们可能需要用到前几级台阶的数据，即 历史记录，所以我们可以用动态规划。
然后依据上面我说的第一步，建立数组 dp[] ，那么顺理成章我们的 dp[i] 应该规定含义为：跳上一个i级的台阶总共有dp[i]种解法。
那么，求解dp[n]就是我们的任务。

制作历史记录表

301

制表

301

填入初始值

301

根据递推关系式，写程序推出剩余的空表项。

注意：这里一维表比较简单可能体现不出它的作用，到二维表它就能很方便的将数据可视化了。

此题，由于明确了数组的含义，我们可以确定是一张一维表。

历史记录表：

数组dp	1	2	3	…	n
值

寻找初始值出口

第二步：找出初始值。
利用我们学过数学归纳法，我们可以知道如果要进行递推，我们需要一个初始值来推出结果值，也就是我们常说的第一张多米诺骨牌。

本题的初始值很容易我们就找出来了，

301

当 n = 1 时

301

当 n = 2 时

301

当 n = 3 时

历史记录表：

数组dp	1	2	3	…	n
值	1	2

找出递推关系式

第三步：找出数组元素之间的关系式。
动态规划有一点类似于数学归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[1]……dp[n-2]、dp[n-1] ，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如， dp[i] = dp[i-1] + dp[i-2] ，这个就是它们的递推关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。

当 n = i 时，即有 i 级台阶，我们的青蛙最后究竟怎么样到达的这第 i 级台阶呢？
因为青蛙的弹跳力有限，只能一次跳一级或者两级，所以我们有两种方式可以到达最后的这第 i 级：

301

所以，我们只需要把青蛙跳上 i-1 级台阶和 i-2 级台阶的跳法加起来，我们就可以得到到达第 i 级的跳法（i≥3），即
\[dp[i] = dp[i-1] + dp[i-2],(i≥3)\]

这样我们知道了初始值dp[1]、dp[2]，可以从dp[3]开始递推出4、5、6、...、n。

历史记录表：

数组dp	1	2	3	…	n
值	1	2	3	…

用程序循环得出后面的空表项。

你看有了初始值，以及数组元素之间的关系式，那么我们就可以像数学归纳法那样递推得到dp[n]的值了，而dp[n]的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

答案：

// 青蛙跳台阶
int f(int n) {
    // 特别给初始值的出口
    if(n <= 2)
        return n;
        
    // 创建数组保存历史数据
    int[] dp = new int[n+1];
    
    // 给出初始值
    dp[1] = 1;
    dp[2] = 2;
    
    // 通过递推关系式来计算出 dp[n]
    for(int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    // 把最终结果返回
    return dp[n];
}

实例

超级青蛙跳台阶

一个台阶总共有 n 级，超级青蛙有能力一次跳到 n 阶台阶，也可以一次跳 n-1 阶台阶，也可以跳 n-2 阶台阶……也可以跳 1 阶台阶。
问超级青蛙跳到 n 层台阶有多少种跳法？（n<=50）

例如：
输入台阶数：3
输出种类数：4
解释：4 种跳法分别是(1,1,1),(1,2),(2,(3)

答案：

这里我是运用了“数学”来得出式子的，为了告诉大家不要拘泥于程序，数学也是一个很有用的工具。

用 Fib(n) 表示超级青蛙

【算法】动态规划四步走

动态规划

适用场景

动态规划四步走

明确数组的含义

制作历史记录表

寻找初始值出口

找出递推关系式

实例

超级青蛙跳台阶

猜你在找的算法相关文章