递推算法与递推套路(算法基础篇)

原创
2021/10/13 18:30
阅读数 908

相信了解算法同学经常会说动态规划太难了,看到题目完全不知从何下手,或者是说“一看题解就会,一看题目就废”这样的一个状态。本质上是由于学习动态规划的时候,学习方法不对,最终导致南辕北辙,没有掌握其中精髓。而动态规划与递推算法又有着暧昧不清的关系,我们选择先从递推算法入手,一步一步揭开动态规划的神秘面纱。

作者/ 汤文辉

编辑/ 黄倩倩(实习)

youdao

一、递推公式

ydtech


每一个递推算法,都有一个递推公式,通过递推公式我们可以更加明确的了解递推算法。


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];
};


youdao

二、数学归纳法

ydtech


上面带着大家一起学习了一下斐波那契数列递推公式的实际应用。那么,为什么上面这个公式就能够描述这一类问题的特性呢?这就要再聊一下数学归纳法了。


数学归纳法在整个计算机科学当中是非常重要的,主要分为以下几步

  1. 验证 k0成立(边界条件);

  2. 证明如果 k(i) 成立,那么 k(i+1) 也成立;

  3. 联合步骤1和步骤2,证明由 k0~k(n) 成立。

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

  1. 验证 k0 成立:在爬楼梯问题中,我们的边界条件就是当 n 为 0和n为1。

  2. 证明如果 k(i) 成立,那么 k(i+1) 也成立:我们假设 res[i-1] 和res[i-2] 是正确的,那么,res[i] 也是成立的。

  3. 联合步骤1和步骤2,证明由 k0~k(n) 成立:由于步骤1和步骤2联立,必然能够得出 res[n] 是成立的。


youdao

三、如何求解递推问题

ydtech


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


  1. 确定递推状态(重点)

  • 一种函数符号 f(x) 以及赋予函数符号一个含义

  1. 例如上面的斐波那契数的求解问题,我们要赋予 f(x) 一个含义:爬上第x阶楼梯的方法总数。

  • 函数所对应的值就是我们要求解的答案

  1. 如:f(x) = y中,x 是自变量,y 是因变量。而在上面爬楼梯的问题当中,自变量x就是要爬的楼梯数,而因变量 y 就是爬到 x 阶楼梯的方法总数。因此,我们在求解问题的时候,最终要的是确定哪个是自变量,哪个是因变量。通常,因变量的值就是我们要求解的值。

  2. 那么,我们要如何分析题目中的自变量是什么呢?我们要确定,会影响因变量的因素有哪些。如爬楼梯问题中,影响方法总数的就只有我们当前要爬的楼梯数,因此,自变量就是楼梯数 x。

  • 思维练习

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

首先第一个会影响我们方法总数的自变量就是 n,即房间被划分成了几个区块,其次,由于房间是环形的,为了不让首尾颜色相同,我们还需要将首尾颜色也记录到我们的递推状态当中,那么,我们就得到了如下的公式

f(n, i, j) = y,其中,n 代表一个房间被分成几个区块,i 和 j 分别代表首尾颜色,y 代表方法总数。

这个公式的意思是:总共有 n 个区块的房间,第一个区块涂第 i 种颜色,最后一个区块涂第 j 种颜色并且相邻颜色不同的方法总数为 y。

  • 递推公式

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

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

    2. 确定递推公式

  • 确定 f(n) 依赖于哪些 f(i) 的值

    3. 分析边界条件 (k0)

    4. 程序实现

  • 递归

  • 循环


youdao

四、递推与动态规划

ydtech


动态规划问题其实就是求解最优化的递推问题,动态规划问题相较于普通的递推问题,多出了一个决策的过程。空讲概念有点抽象,我们来结合具体问题来分析。依旧还是爬楼梯问题,不过比之前的爬楼梯多了一个体力花费

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];
};

youdao

五、结语

ydtech

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

-END-

往期推荐

本文分享自微信公众号 - 有道技术团队(youdaotech)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
1 评论
0 收藏
0
分享
返回顶部
顶部