【每日一题】JZ9 跳台阶扩展问题

当你的才华还撑不起你的野心时，你应该静下心去学习 。 题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

示例

输入：3
返回值：4

解题思路

对于方法一中的：f[n] = f[n-1] + f[n-2] + … + f[0]

那么f[n-1] 为多少呢？

f[n-1] = f[n-2] + f[n-3] + … + f[0]

所以一合并，f[n] = 2*f[n-1]，初始条件f[0] = f[1] = 1

所以可以采用递归，记忆化递归，动态规划，递推。具体详细过程，可查看青蛙跳台阶。

复杂度分析： 时间复杂度 O(N) ： 计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。 空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。

参考代码 Java版本

public class Solution {//规律是f(n) = f(n-1)
    public int JumpFloorII(int target) {
        int sum = 1;
        if(target == 0)
            return 0;
        for(int i = 1;i