题解 | 跳台阶扩展问题

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        System.out.println(run(n));
    }

    public static int run(int n){
           // 边界条件
        if (n == 0) return 0; // 如果n为0，返回0
        if (n == 1) return 1; // 如果n为1，返回1
        if (n == 2) return 2; // 如果n为2，返回2
        if (n == 3) return 4; // 如果n为3，返回4

        // 创建dp数组，长度为n+1
        int[] dp = new int[n + 1];

        // 初始化dp数组
        dp[0] = 0; // 0步有0种方法
        dp[1] = 1; // 1步有1种方法
        dp[2] = 2; // 2步有2种方法
        dp[3] = 4; // 3步有4种方法

        // 动态规划计算  为2的等比数列
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1]*2; // 状态转移方程
        }

        return dp[n]; // 返回结果
    }
}