题解 | #NC68 跳台阶#

跳台阶

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

感觉这道题相比NC65 斐波那契数列,更适合拿来当作动态规划的入门训练题,因为相比 Fibonacci 数列已经给好了递推公式,这道题需要自己从实际问题中抽象出问题模型,虽然最终抽象出来还是 Fibonacci 数列哈。

下面是过程分析。

已知:

  1. 爬到第 1 阶,只可能也只用爬 1 阶就能完成,共 1 种爬法
  2. 爬到第 2 阶,可能是从先爬 1 阶到第 1 阶,然后再爬 1 阶到第 2 阶;也可能是直接爬 2 阶到第 2 阶,一共 2 种爬法
  3. 爬到第 3 阶,可能直接来自于第 1 阶(一共 2 阶的距离),也可能来自于第 2 阶(一共 1 阶的距离),而如何爬到第 1 阶和第 2 阶?有多少种爬法?则回到了步骤 1 和 2
  4. 归纳一下:在第 n 阶时,可能是由从第 n-2 阶爬 2 阶达到,也可能由从第 n-1 阶爬 1 阶达到(n>2)

记录 爬到第 n 阶时可能有多少种爬法,则:

暴力递归

int jumpFloor(int n) {
    if (n == 1 || n == 2)
        return n;
    return jumpFloor(n-2) + jumpFloor(n-1);
}

此方法存在 2 个问题:

  1. 存在大量重复计算,比较耗时
  2. 由于是递归,比较消耗栈空间

记忆递归

int helper(int* f, int n) {
    if (n == 1 || n == 2)
        f[n] = n;
    else if (f[n] == 0) // n>2 且 f[n] 未更新
        f[n] = helper(f, n-2) + helper(f, n-1);
    return f[n];
}

int jumpFloor(int n) {
    int f[n+1]; // f[n] 记录爬到第 n 阶有多少种方法
    memset(f, 0, sizeof(int)*(n+1)); // 此次值得注意,是以字节为单位去初始化的
    return helper(f, n);
}

还剩下一个问题:递归栈比较长

可以尝试转化为迭代

递推迭代

int jumpFloor(int n) {
    if (n == 1 || n == 2) 
        return n;
    int f[n+1]; // f[n] 记录爬到第 n 阶有多少种方法
    memset(f, 0, sizeof(int)*(n+1));
    f[1] = 1; f[2] = 2;
    for (int i = 3; i <= n; ++i) {
        f[i] = f[i-2] + f[i-1]; // 状态转移
    }
    return f[n];
}

本题要求的只是爬到第 n 阶有多少种爬法,所以不必保存爬到所有阶对应的爬法计数。

根据递推关系 ,可知,与第 n 项有直接关系的只有第 n-1 和 n-2 项,所以只需保存这 3 个位置

递推迭代+状态压缩

int jumpFloor(int n) {
    if (n == 1 || n == 2) 
        return n;
    int pre2 = 1, pre1 = 2, curr;
    for (int i = 3; i <= n; i++) {
        curr = pre2 + pre1;
        pre2 = pre1;
        pre1 = curr;
    }
    return curr;
}

还可以简化成只记录 2 个位置

递推迭代+状态压压缩

int jumpFloor(int n) {
    if (n == 1 || n == 2)
        return n;
    int pre = 1, cur = 2;
    for (int i = 3; i <= n; i++) {
        cur = pre + cur;
        pre = cur - pre;
    }
    return cur;
}
全部评论
点赞 回复 分享
发布于 02-13 03:11 四川
dalao
点赞 回复 分享
发布于 2022-12-04 18:17 四川

相关推荐

不愿透露姓名的神秘牛友
今天 12:31
以前小时候我最痛恨出轨、偷情的人,无论男女,为什么会出轨?现在我成了自己最讨厌的人,没想到分享的东西在牛客会被这么多人看,大家的评价都很中肯,我也认同,想过一一回复,但我还是收声了,我想我应该说说这件事,这件事一直压在我心里,是个很大的心结,上面说了人为什么出轨,我大概能明白了。我们大一下半年开始恋爱,开始恋爱,我给出了我铭记3年的承诺,我对她好一辈子,我永远不会背叛,我责任心太重,我觉得跟了我,我就要照顾她一辈子,我们在一起3年我都没有碰过她,她说往东我就往东,她说什么我做什么,她要我干什么,我就干什么!在学校很美好,中途也出过一些小插曲,比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了,我...
牛客刘北:两个缺爱的人是没有办法好好在一起的,但世界上哪有什么是非对错?你后悔你们在一起了,但是刚刚在一起的美好也是真的呀,因为其他人的出现,你开始想要了最开始的自己,你的确对不起自己,21岁的你望高物远,你完全可以不谈恋爱,去过你想要的生活,你向往自由,在一起之后,你要想的不是一个人,而是两个人,你不是变心了,就像你说的,你受够了,你不想包容了,冷静几天是你最优的选择,爱人先爱己。
社会教会你的第一课
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
评论
18
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务