递推算法与递推套路（算法基础篇）前端客户端算法网易

文章图片

联系我们：有道技术团队助手：ydtech01 / 邮箱：[ydtech@rd.netease.com]
相信了解算法同学经常会说动态规划太难了，看到题目完全不知从何下手，或者是说“一看题解就会，一看题目就废”这样的一个状态。本质上是由于学习动态规划的时候，学习方法不对，最终导致南辕北辙，没有掌握其中精髓。而动态规划与递推算法又有着暧昧不清的关系，我们选择先从递推算法入手，一步一步揭开动态规划的神秘面纱。
一、递推公式每一个递推算法，都有一个递推公式，通过递推公式我们可以更加明确的了解递推算法。
1.1 斐波那契数列的递推公式
f(n) = f(n-1) + f(n-2) ,这是我们斐波那契数列的递推公式，有很多同学可能会问，这个公式实际有什么用呢？接下来，我们来直接看一个算法题：爬楼梯
LeetCode 70. 爬楼梯这道题我们要怎么理解呢？我们如果想要爬到第 n 阶楼梯，那么上一步有可能是在 n-1 ,也有可能是在 n-2

文章图片

因此，这道题的解法就一目了然了：

function climbStairs(n: number): number { const res: number[] = []; // 爬到第0层的方法就是一动不动，我们可以认为他只有一种 res[0] = 1; // 爬上第一层阶梯的可能性只有1个，就是走一步 res[1] = 1; // 因此，后面的爬楼方式，我们就可以通过地推方式计算出来 for(let i=2; i<=n; i++) { res[i] = res[i-1] + res[i-2]; } return res[n]; };

二、数学归纳法上面带着大家一起学习了一下斐波那契数列递推公式的实际应用。那么，为什么上面这个公式就能够描述这一类问题的特性呢？这就要再聊一下数学归纳法了。
数学归纳法在整个计算机科学当中是非常重要的，主要分为以下几步：

验证k0成立（边界条件）；
证明如果k(i)成立，那么k(i+1)也成立；
联合步骤1和步骤2，证明由k0~k(n)成立。

不知道大家是否还记得，之前我们学习二叉树时，有扩展学习过递归程序的设计，而递归程序的设计要点就是数学归纳法在广义方面的应用，又称为结构归纳法。
那么，我们再来看一下上面的爬楼梯问题，怎么使用数学归纳法分析。

验证k0成立：在爬楼梯问题中，我们的边界条件就是当n为0和n为1。
证明如果k(i)成立，那么k(i+1)也成立：我们假设 res[i-1] 和 res[i-2] 是正确的，那么，res[i]也是成立的。
联合步骤1和步骤2，证明由k0~k(n)成立：由于步骤1和步骤2联立，必然能够的出res[n]是成立的。

三、如何求解递推问题（递推问题的求解套路）

论求解套路的重要性：求解套路就是递推算法的学习方式，如果学习方式错了，很可能南辕北辙，花了比别人更多的时间，反而掌握的更少。就像健身的时候，如果你掌握了一些动作要领，可能1~2个月肌肉就出来了，但是你要是没有掌握动作要领，练错了，不仅长得肌肉变成肥膘，还可能伤到自己。

确定递推状态（重点）
- 一种函数符号 f(x) 以及赋予函数符号一个含义
  - 例如上面的斐波那契数的求解问题，我们要赋予 f(x) 一个含义：爬上第x阶楼梯的方法总数
- 【递推算法与递推套路（算法基础篇）】函数所对应的值就是我们要求解的答案
  - 如：f(x) = y 中， x是自变量， y 是因变量。而在上面爬楼梯的问题当中，自变量x就是要爬的楼梯数，而因变量 y 就是爬到 x 阶楼梯的方法总数。因此，我们再求解问题的时候，最终要的是确定哪个是自变量，哪个是因变量。通常，因变量的值就是我们要求解的值。
  - 那么，我们要如何分析题目中的自变量是什么呢？我们要确定，会影响因变量的因素有哪些。如爬楼梯问题中，影响方法总数的就只有我们当前要爬的楼梯数，因此，自变量就是楼梯数 x。
- 思维练习

文章图片

首先来分析一下递推状态是什么。

首先第一个会影响我们方法总数的自变量就是 n ，即房间被划分成了几个区块，其次，由于房间是环形的，为了不让首尾颜色项目，我们还需要将首尾颜色也记录到我们的递推状态当中，那么，我们就得到了如下的公式：
f(n, i, j) = y，其中，n代表一个房间被分成几个区块，i 和 j 分别代表首尾颜色， y 代表方法总数。这个公式的意思是：总共有n个区块的房间，第一个区块涂第i种颜色，最后一个区块涂第j种颜色并且相邻颜色不同的方法总数为y

递推公式
上面分析得出了 f(n, i, j) = y 这样一个简易版的公式，现在，我们就需要确定，通过怎样的运算能够算出f(n, i, j)

文章图片

注意，上面三个递推公式都是正确的，只是在不断的优化我们的递推公式，提升程序效率，但三种方式都可以求解出正确答案

确定递推公式
- 确定 f(n) 依赖于哪些 f(i) 的值
分析边界条件(k0)
程序实现
- 递归
- 循环

四、递推与动态规划动态规划问题其实就是求解最优化的递推问题，动态规划问题相较于普通的递推问题，多出了一个决策的过程
空讲概念有点抽象，我们来结合具体问题来分析。依旧还是爬楼梯问题，不过比之前的爬楼梯多了一个体力花费。
LeetCode 746. 使用最小花费爬楼梯
这道题与上面简单的爬楼梯问题类似，差别就在于每上一层楼梯，我们需要花费一定的体力，要求我们求出花费最小的体力。

文章图片

通过上面的分析，我们可以得出以下公式：dp[n] = min(dp[n-2] + cost[n-2], dp[n-1] + cost[n-1])
翻译一下上面的公式：爬上第n层楼梯的总体力花费应该等于最后一步从第n-2层爬上来的体力花费与最后一步是从n-1层爬上来的体力花费的最小值

function minCostClimbingStairs(cost: number[]): number { const n = cost.length; const dp: number[] = []; // 由于题目给定可以从第0层或第1层开始爬，因此，我们初始化第0层和第1层的体力花费为0 dp[0] = 0; dp[1] = 0; // 我们从第二层的体力花费开始递推 for(let i=2; i<=n; i++) { // 第i层的体力花费是我最后一步从i-1层爬上来的体力花费与从i-2层趴上来的体力花费的最小值 dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[n]; };

五、结语大家都觉得动态规划学起来很难，主要是因为我们要真正学好动态规划，需要从：递推状态定义、状态转移方程推导、程序实现等三个大方向上入手并学习，并且这三个方向都是不好学的。今天通过递推算法与递推公式的相关学习，以及初步的了解了递推算法与动态规划的关系。这些都是我们后续学习动态规划的基础，其中尤为重要的是数学归纳法的理解与应用。“光说不练假把式”，今天说的大部分都是理论，下一篇文章《递推算法与递推套路（手撕算法篇）》将会直接从一些递推或动态规划的题目入手，学习递推程序或动态规划程序的求解套路，让你看到递推和动规不再茫然。敬请期待！