[NC]261. 跳台阶扩展问题

🚩传送门：牛客题目

题目

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

数据范围：
进阶：空间复杂度 ， 时间复杂度

示例1

输入：3 输出：4

解题思路：动态规划

👉 定义： 表示青蛙跳上第 个台阶总共的跳法数 。

那么我们不难发现显然

1是青蛙直接选择跳上第 个台阶

由于
然而

🚩综上，状态转移方程：

因此对于一个级的台阶，只需要将 即可

因为

复杂度分析

时间复杂度： ，其中 是字符串长度，其中 是字符串长度。

空间复杂度： ，即为存储所有状态使用的空间。

我的代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() - 1;
        System.out.println(1 << n);    // 对于dp[5],只需要将 1 右移 4 次即可
    }
}