上台阶问题-递归和动态规划

上台阶是一个常见的问题，解法主要有递归和利用动态规划，这篇文章简单介绍下递归解法和动态规划，以及对应的代码。递归解答这个问题相对比较好理解，如下：

问题

现有n级台阶或者楼梯，其中n取值大于1的正整数，假定每次可以进行上1级-2级楼梯，求n级台阶对应的所有上台阶的方法。

分析

当n=1的时候，只有1种方法，当n=2，则有1+1，2，合计两种方法。这是正向的来推导，其他没有什么特别的规律。换个思路，设定n对应上台阶的方法数为f(n)，假如上1级，则剩余台阶的方法数为f(n-1)；假如上2级，剩余台阶的方法数为f(n-2)，所以n级台阶对应的方法数就是f(n)=f(n-1)+f(n-2)之和。同时考虑当n=0，n<0时的特殊情况，其实就是n=1,n=2的时候f(n)对应的值。

动态规划思路，之后的结果依赖之前的计算，获取最优子结果，用一个temp保存上一步计算，同时再将temp作为下一步计算，得到最终结果，如下的countWays方法。

代码

综上的分析，我们得到的代码如下：

public class Upstairs {

    public static void main(String[] args) {
        System.out.println(steps(1));
        System.out.println(steps(2));
        System.out.println(steps(3));
        System.out.println(steps(15));

    }

    public static int steps(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if( n == 2){
              return 2;
        }

        return steps(n - 1) + steps(n - 2);
    }

     public static int countWays(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        int a = 1;
        int b = 2;
        int temp = 0;

        for (int i = 3; i < n + 1; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
}