JZ8 — 跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

题目分析

这道题和上一题是相同的题目,递归或者递推都可以解决,不再赘述。
参考:http://www.guanhaobo.cn/?p=684

青蛙跳上第n级台阶,一共有两种方式:
1. 从第n-1级台阶一次跳上1级台阶到达第n级台阶
2. 从第n-2级台阶一次跳上2级台阶到达第n级台阶

因此有f[n] = f[n-1] + f[n-2]

C++

class Solution
{
public:
    int jumpFloor(int number)
    {
        if (number < 3)
            return number;
        int a3, a2 = 2, a1 = 1;
        for (int i = 3; i <= number; i++)
        {
            a3 = a2 + a1;
            a1 = a2, a2 = a3;
        }
        return a3;
    }
};

Java

public class Solution {
    public int JumpFloor(int target) {
        if (target < 3)
            return target;
        int a3 = 3, a2 = 2, a1 = 1;
        for (int i = 3; i <= target; i++) {
            a3 = a2 + a1;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }
}

一个回复在 “JZ8 — 跳台阶

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部