【动态规划】【leetcode70改编题目】爬楼梯

【动态规划】【leetcode70改编题目】爬楼梯

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

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

注意：给定 n ,m是一个正整数。

示例1：
输入： m=2,n=2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

解答：

class Solution:
    def climbStairs(self, m:int, n: int) -> int:
        #dp[i]: 凑成目标正整数为i的排列个数
        dp=[0]*(n+1)
        dp[0]=1
        #先遍历背包，再遍历物品，以求排列
        for j in range(1,n+1):
            for step in range(1,m+1):
                if j>=step:
                    dp[j]+=dp[j-step]
        return dp[n]