爬楼梯进阶版

爬楼梯进阶版

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 ,2 ,3…m个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入： n = 3 ，m = 3 输出：4

解释： 有四种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶

1阶 + 2 阶

2 阶 + 1 阶

3 阶

解题思路

动态规划

此题为爬楼梯的升级版，解题思路同[组合总和Ⅳ](./15. 组合总和 Ⅳ.md)

其实就是多重背包的排列问题

把1，2，3…m看成物品，n看成背包容量，问有多少种排列可以装满背包

1.确定dp数组及下标的含义

dp[i] 表示达到n阶楼梯有多少种方法

2.确定递推公式

求装满背包有几种方法，一般递推公式都为dp[i] + = dp[i - nums[j]]

物品的容量为 1，2，3…m，用 j 表示物品的容量

若不考虑 j 装满容量 i - j背包，有dp[i - j]种方法，

如果把 j 装入正好装满容量为j的背包，凑成dp[i]就有dp[i - j]种方法

本题的递推公式为 dp[i] += dp[i - j];

3.初始化dp数组

dp[0] = 1，背包容量为0有一种方法，表示什么都不放，该值必须初始化为1，否则无法递推下去

4.确定遍历顺序

如果先遍历物品，在遍历背包容量，求的是组合有多少种方法

本题要先遍历背包容量，再遍历物品，求的是排列有多少种方法

又本题是多重背包问题，物品可以重复使用，要从小到大遍历背包容量

代码

public static void main(String[] args){
        System.out.println(climbStairs(3,3)); //4
    }

    static int climbStairs(int n, int m){
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i = 1 ; i <= n ; i++){ //遍历背包
            for(int j = 1; j <=m ; j++){ //遍历物品
                if(i>=j){
                    dp[i] += dp[i - j];
                }
            }
        }
        return dp[n];
    }

• 时间复杂度：$O(n × m)$

• 空间复杂度：$O(n)$