今日算法10-变态跳台阶

一、题目描述

题目链接：牛客网

难易程度：简单

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

二、解题思路

动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；

对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

跳上 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(1) 和 f(2) 可以提前算出来：

f(1) = 1
f(2) = 2

复杂度分析

时间复杂度 O(N) ：计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。

空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。

三、代码实现

public int jumpFloorII(int target) {
    int[] dp = new int[target + 1];
    //初始化前面两个
    dp[1] = 1;
    dp[2] = 2;
    //依次乘2
    for(int i = 3; i <= target; i++)
        dp[i] = 2 * dp[i - 1];
    return dp[target];
}

推荐阅读

• 今日算法07-斐波那契数列
• 今日算法09-青蛙跳台阶问题

封面

今日算法系列，题解更新地址：https://studeyang.tech/2023/0731.html