JZ71 跳台阶扩展问题

发表于 分类于 本文字数： 422 阅读时长 ≈ 2 分钟

JZ71 跳台阶扩展问题

描述

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

数据范围：$1≤n≤20$
进阶：空间复杂度 $O(1)$ ， 时间复杂度 $O(1)$

示例1

1
2
输入：3
返回值：4

示例2

1
2
输入：1
返回值：1

题解

首先，根据跳台阶基础版，考虑最后一次跳了几阶，从一阶开始，最后跳一阶的话$dp[i-1]$种跳法，跳两阶则有$dp[i-2]$种，以此类推则可以分析出$dp[i]=1(直接跳i阶)+dp[i-1]+dp[i-2]+……+dp[1]$同时$dp[1] = 1，dp[2]=2$,由此我们就可以进行递归了。

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloorII(int number) {
        if(number==1) return 1;
        if(number==2) return 2; 
        int ans = 1;
        for(int i = 1; i < number; i++){
            ans += jumpFloorII(i);
        }
        return ans;
    }
};

优化：当然从递推公式也可以看出来这个实际上是可以求和的，即是直接求$dp[i]$。
$$
a_i = 1+s_{i-1}\
a_{i+1} = 1+s_{i}
$$
由此可得
$$
a_{i+1}-a_{i} = a=i 即a{i+1} = 2a_i
$$
所以$dp[i]$是一个等比数列，求第n项的方法就是$2^{n-1}*a_1$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloorII(int number) {
        return pow(2,number-1);
    }
};