爬楼梯问题

假设小明住在二楼，每次回家都需要经过一个有10层台阶的楼梯。小明每次可以选择一步走一级台阶或者一步走两级台阶。小明从楼下到家一共有多少种走法？

首先，从后往前分析问题的最优子结构。

考虑小明走最后一步的情况，他要么是从第九级台阶再走一级到第十级，要么是从第八级台阶走两级到第十级。也就是说，要想到达第十级台阶，最后一步一定是从第八级或者第九级台阶开始的。

为了描述方便，用F(n)表示第n级台阶的走法数量。

也就是说，如果已知从地面到第八级台阶F(8)一共有X种走法，从地面到第九级台阶F(9)一共有Y种走法，那么从地面走到第十级台阶F(10)一定是X和Y之和，即F(10)=F(9)+F(8)。这是因为最后一步只有两种走法，所以倒数第二步只有两种情况。

F(n)的最优解，包含了子问题F(n-1)和F(n-2)最优解，这是应用动态规划的一个重要基础。

之后要注意初始条件的确定，即当只有一级和两级台阶时的情况，因为F(0)往前对于该问题是没有意义的。

由于问题比较简单，可以直接分析得出，该问题的初始条件为F(1)=1、F(2)=2。所以到达二级台阶有两种情况。

所以该问题作为动态规划问题求解的要素如下。

初始条件：F(1)=1，F(2)=2。

最优子结构：F(n)的最优子结构即F(n-1)和F(n-2)。

状态转移函数：F(n)=F(n-1)+F(n-2)。

台阶数量为3时，根据状态转移函数，可知F(3)=F(2)+F(1)=3

台阶数量为4时，根据状态转移函数，可知F(4)=F(3)+F(2)=5

代码：

def goUpStairs(n):
    if n < 1:  # 判断当前台阶级数小于1
        return 0
    if n == 1:  # 判断当前台阶级数为1
        return 1
    if n == 2:  # 判断当前台阶级数为2
        return 2
    a = 1  # 初始化边界值
    b = 2
    sum = 0
    for i in range(2, n):  # 迭代求解各级台阶的走法数量
        sum = a + b
        a = b
        b = sum
    return sum   # 输出计算结果

可以尝试加入列表：

def stairs(n):
    if n <= 1:
        return n
    dp = [1] * (n+1)
    # 第一个台阶只能有一种跳法
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]  # 跳到第i个台阶，可以是从前一个台阶跳过来，也可以是从前二个台阶跳上来
    return dp[n]

可以尝试递归：

def generic(n):
    if n <= 2:
        return n
    return generic(n-2)+generic(n-1)