跳台阶.NC68

81 阅读 0 评论 54 点赞

我是靠谱客的博主痴情煎饼，这篇文章主要介绍跳台阶.NC68，现在分享给大家，希望可以做个参考。

题目描述

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

输入

1

返回值

1

题解

动态规划:第n次状态取决与n-1次和n-2次的总和,即a[n] = a[n-1] + a[n-2]; 因为每次只能跳一步或者两步. 这里为了简单我设res[0]=1.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int JumpFloor(int target) {
        int[] res = new int[target + 1];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i <= target; i++) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[target];
    }
}

更明确的写法:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int JumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        int[] res = new int[target + 1];
        res[1] = 1;
        res[2] = 2;
        for (int i = 3; i <= target; i++) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[target];
    }
}

递归: 用时更长

复制代码

1
2
3
4
5
6
7
8
9
public class Solution {
    public int JumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        return JumpFloor(target - 1) + JumpFloor(target - 2);
    }
}