【算法】动态规划

# 动态规划 > **动态规划**(dynamic programming)：它是把研究的问题分成若干个阶段，且在**每一个阶段**都要“动态地”做出决策，从而使整个阶段都要取得最优效果。 >> **理解：**其实，无非就是利用**历史记录**，来避免我们的重复计算。 而这些历史记录，我们得需要一些变量来保存，一般是用**一维数组**或者**多维数组**来保存。 其实我挺好奇为什么用动态规划这个名字的，所以我花时间找了一下，如果大家想要知道这个名字的由来，可以去看看：[动态规划](https://en.wikipedia.org/wiki/Dynamic_programming#History) ## 动态规划四步走 **动态规划四步走：** - **明确数组的含义：**建立数组，明确数组元素的含义； - **制作历史记录表：**根据数组建表，填入初始值，利用递推关系式写程序推出其他空表项。 > **注意：**这个是为我们通过初始值和递推关系式写出程序提供可视化条件以及思路，把抽象的东西可视化了，时时刻刻都知道自己要干嘛。 当然，如果脑子里有思路可以忽略。。 - **寻找数组初始值：**寻找数组元素初始值； > **注意：**这个**初始值**要特别的给出一个**出口**，因为它们不是被递推出来的。 - **找出递推关系式：**找出数组元素递推关系式。 > **注意：**可以从 **dp[i] = ?** 这一数学公式开始推想。 ### 明确数组的含义 > **第一步：**定义数组元素的含义。 上面说了，我们会用一个数组，来保存历史记录，假设用一维数组 dp[]吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，即 你的 dp[i] 是代表什么意思？ 那么下面我来举个**例子**吧！ **问题描述：**一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 首先，拿到这个题，我们需要判断用什么方法，要跳上n级的台阶，我们可能需要用到前几级台阶的数据，即 **历史记录**，所以我们可以用**动态规划**。 然后依据上面我说的第一步，建立数组 dp[] ，那么顺理成章我们的 dp[i] 应该规定含义为：**跳上一个i级的台阶总共有dp[i]种解法**。 那么，求解dp[n]就是我们的任务。 ### 制作历史记录表 1. 根据数组，**制表**，确定一维表、二维表； 2. **填入初始值**； 3. 根据递推关系式，写程序**推出剩余的空表项**。 > **注意：**这里一维表比较简单可能体现不出它的作用，到二维表它就能很方便的将数据可视化了。 此题，由于明确了数组的含义，我们可以确定是一张一维表。 **历史记录表：** |数组dp|1|2|3|…|n| |---|---|---|---|---|---| |值| | | | | | ### 寻找数组初始值 > **第二步：**找出初始值。 利用我们学过数学归纳法，我们可以知道如果要进行递推，我们需要一个初始值来推出结果值，也就是我们常说的第一张多米诺骨牌。 本题的初始值很容易我们就找出来了， - **当 n = 1 时**，即 只有一级台阶，那么我们的青蛙只用跳一级就可以了，只有一种跳法，dp[1] = 1； - **当 n = 2 时**，即 有两级台阶，我们的青蛙有两种选择，一级一级的跳 和 一次跳两级，dp[2] = 2； - **当 n = 3 时**，即 有三级台阶，我们的青蛙跳一级 + dp[2]，或 跳两级 + dp[1]，这时候我们就反应过来了，需要进行下一步找出 n 的递推关系式。 --- **历史记录表：** |数组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 级： - 从 i-1 处跳一级 - 从 i-2 处跳两级 所以，我们只需要把青蛙跳上 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,1),(3) --- **答案：** > 这里我是运用了**“数学”**来得出式子的，为了告诉大家不要拘泥于程序，数学也是一个很有用的工具。 用 **Fib(n)** 表示超级青蛙