climbStairs.java

// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 或 3 个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        if (n < 4) return dp[n];
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 或 3 个台阶，但相邻的两步不能爬相同个数的台阶，你有多少种不同的方法可以爬到楼顶呢？
class Solution {
    public int climbStairs(int n) {
        if (n < 3) return 1;
        int[][] dp = new int[n + 1][4];
        dp[3][1] = dp[2][2] = 1;
        dp[3][2] = dp[1][1] = 1;
        dp[3][3] = 1;
        for (int i = 4; i <= n; i++) {
            dp[i][1] = dp[i - 1][2] + dp[i - 1][3];
            dp[i][2] = dp[i - 2][1] + dp[i - 2][3];
            dp[i][3] = dp[i - 3][1] + dp[i - 3][2];
        }
        return dp[n][1] + dp[n][2] + dp[n][3];
    }
}