台阶问题（动态规划算法）

问题描述：

有个高度为10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要到达最上面问一共有多少种走法？

问题分析：

解法一：穷举法（该方法往往不是最有效，但往往是最直接的解决问题的方法）

解法二：动态规划法

目标要想找到到达从0阶到10阶，那么最后的一步要么是从第8阶到第10阶，要么是从第9阶到第10阶，于是将问题转化为两部分之和：

（1） 从0阶到第8阶的方法

（2） 从0阶到第9阶的方法

我们可以用公式表达为F（0,10）= F（0,9）+ F（0,8）

F（0,N）表示从0阶到第N阶的方法

同样道理：F（0,9） = F（0,8）+ F（0,7）

于是存在如下递推关系：

F（0,N） = F（0,N-1）+ F（0,N-2） （N > 2）

F（0,1）= 1

F（0,2）= 2

这和斐波那契数列的递推关系是类似的，于是代码实现如下（python语言）：

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def compute1(N):
    '''
    递归实现
    :param N: 第N阶台阶
    :return:
    '''
    if N<= 0:
        return "parameter invalid."
    elif N == 1:
        return 1
    elif N == 2:
        return 2
    else:
        return compute1(N- 1) + compute1(N - 2)
 
def compute2(N):
    '''
    非递归实现
    :param N: 第N阶台阶
    :return: c 从第0阶到第N阶总的方法
    '''
    if N <= 0:
        return "parameter invalid."
    elif N == 1:
        return 1
    elif N == 2:
        return 2
    else:
        a, b, c = 1, 2, 0
        while N >2:
            c = a + b
            a, b = b, c
            N -= 1
        return c
 
if __name__ == "__main__":
    print compute1(-5)
    print compute2(5)

上面思考问题是从最后一步有几种方法的角度入手
那么如果从第一步有几种方法的角度入手是不是也有相似的递推关系呢？我们来分析下：

第一步存在两种方法：（1）一个台阶，还剩 9个（2）2个台阶，还剩8个

那么从第0阶到第10阶的方法 = 剩余9个台阶的方法（从第1阶到第10阶的方法） + 剩余8个台阶的方法（从第2阶到第10阶的方法）

我们用公式表示为：

G（0,10） = G（1,10） + G（2,10）

G（N,10）表示从第N阶到第10阶的方法数。

同样：

G（1,10） = G（2,10） + G（3,10）

G（2,10） = G（3,10） + G（4,10）

于是存在如下递推关系：

G（N,10） = G（N + 1,10） + G（N + 2,10） （N + 2 <= 9）

G（8,10） = 2

G（9,10） = 1

代码实现如下（python语言）：

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def compute1(N, M):
    '''
    递归实现
    :param N: 第N阶台阶
    :param M: 总的台阶数
    :return:
    '''
    if  N < 0 or N >= M:
        return "parameter invalid."
    elif N == M- 1 :
        return 1
    elif N == M- 2:
        return 2
    else:
        return compute1(N+ 1, M) + compute1(N + 2, M)
 
def compute2(N, M):
    '''
    非递归实现
    :param N: 第N阶台阶
    :param M: 总的台阶数
    :return:
    '''
    if  N < 0 or N >= M:
        return "parameter invalid."
    elif N == M- 1 :
        return 1
    elif N == M- 2:
        return 2
    else:
        a, b, c = 1, 2, 0
        while N <M - 2:
            c = a + b
            a, b = b, c
            N += 1
        return c
 
if __name__ == "__main__":
    print compute1(0, 5)
    print compute2(0, 5)

上述两种方法分别称为前向动态规划方法（顺序解法）和后向动态规划方法（逆序解法）。