题解 | #跳台阶#

递归

int jumpFloor(int number) {
    if(number <= 1) return 1;
    return jumpFloor(number - 1) + jumpFloor(number - 2);
}

记忆化搜索

int f[50]{0};
int jumpFloor(int number) {
    if(number <= 1) return 1;
    if(f[number] > 0) return f[number];
    return f[number] = (jumpFloor(number - 1) + jumpFloor(number - 2));
}

动态规划

当n=0时 从0个台阶跳到0个台阶 就只有一种方法=》不跳 所以dp[0] = 1

为了保证在递推的时候不会出现数组越界情况

int dp[50]{0};
int jumpFloor(int number) {
    dp[0] = 1, dp[1] = 1;
    for(int i = 2; i <= number; i ++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[number];
}