读书不作儒生酸，跃马西入金城关。

10.4 变态跳台阶

题目链接

牛客网

题目描述

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


解题思路

动态规划

public int jumpFloorII(int target) {
    int[] dp = new int[target];
    Arrays.fill(dp, 1);
    for (int i = 1; i < target; i++)
        for (int j = 0; j < i; j++)
            dp[i] += dp[j];
    return dp[target - 1];
}

数学推导

跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去…，那么

f(n-1) = f(n-2) + f(n-3) + ... + f(0)

同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去… ，那么

f(n) = f(n-1) + f(n-2) + ... + f(0)

综上可得

f(n) - f(n-1) = f(n-1)

即

f(n) = 2*f(n-1)

所以 f(n) 是一个等比数列

public int JumpFloorII(int target) {
    return (int) Math.pow(2, target - 1);
}

版权声明：如无特别声明，本站收集的文章归  cs-notes  所有。 如有侵权，请联系删除。

联系邮箱： [email protected]

本文标题：《 10.4 变态跳台阶 》

本文链接：/%E9%9D%A2%E8%AF%95%E5%88%B7%E9%A2%98/%E5%89%91%E6%8C%87offer%E9%A2%98%E8%A7%A3/%E9%A2%98%E8%A7%A3/10.4-%E5%8F%98%E6%80%81%E8%B7%B3%E5%8F%B0%E9%98%B6.html

Contents