跳台阶.NC68

题目描述

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

输入

1

返回值

1

题解

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

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

更明确的写法:

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

递归: 用时更长

public class Solution {
    public int JumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        return JumpFloor(target - 1) + JumpFloor(target - 2);
    }
}

最后

以上就是痴情煎饼最近收集整理的关于跳台阶.NC68的全部内容，更多相关跳台阶内容请搜索靠谱客的其他文章。