Python 实现阶梯问题：动态规划解法

Python 实现阶梯问题：动态规划解法

阶梯问题是一个经典的算法问题，要求你计算爬上n级阶梯的所有可能性。假设每次你可以爬 1 级或者 2 级，那么如何计算所有可能的爬楼梯方法呢？

由于阶梯问题较为复杂，我们可以采用动态规划的思想来解决。具体思路如下：

1. 定义一个数组 count，count[i] 表示爬上 i 级阶梯的所有可能性；
2. 初始化数组 count，count[0]=1，count[1]=1，表示爬 0 级和 1 级阶梯的方式只有 1 种；
3. 从第 2 级阶梯开始，计算每一级阶梯的可能性，计算方法为 count[i]=count[i-1]+count[i-2]；
4. 返回 count[n]，表示爬上 n 级阶梯的所有可能性；
5. 根据 count[n] 的值，输出可能性和所有可能的结果。

下面是实现代码：

def climbStairs(n: int) -> List[int]:
    if n <= 1:
        return [1]
    count = [0] * (n+1)
    count[0] = 1
    count[1] = 1
    for i in range(2, n+1):
        count[i] = count[i-1] + count[i-2]
    return count

n = int(input())
count = climbStairs(n)
if count[n] == 0:
    print("0")
else:
    print(count[n])
    result = []
    i = n
    while i >= 2:
        if count[i-1] >= 1 and count[i-2] >= 1:
            result.append(str(i-1))
            result.append(str(i-2))
            i -= 2
        elif count[i-1] >= 1:
            result.append(str(i-1))
            i -= 1
        elif count[i-2] >= 1:
            result.append(str(i-2))
            i -= 2
    if i == 1:
        result.append(str(i))
    print(','.join(result[::-1]))

输入样例：

4

输出样例：

5
3,1

**解释：**爬上 4 级阶梯的所有可能性为 5，分别是 1+1+1+1、1+1+2、1+2+1、2+1+1、2+2，所以输出 5 和所有可能的结果 3,1。

总结：

本文介绍了如何使用动态规划解决阶梯问题，并提供了完整的 Python 代码实现。通过学习本文，你可以了解动态规划的基本思想和应用，并尝试用它解决其他类似的算法问题。