动态规划-爬楼梯-Java实现(1)

有一座高10级台阶的楼梯，从下往上走，一次只能向上1级或2级台阶，一共有多少种走法？

结题思路：

1.递归：时间复杂度 2^n
2.备忘录算法：时间复杂度n
3.动态规划：时间复杂度n

// 1.递归：时间复杂度 2^n
private static int stepCount(int count) {
        if (count < 1) {
            return 0;
        }
        if (count <= 2) {
            return count;
        }
        return stepCount(count - 1) + stepCount(count - 2);
    }

//2.备忘录算法：时间复杂度n
private static int stepCount2(int count, Map<Integer,Integer> map) {
        if (count<1){
            return 0;
        }
        if (count<=2){
            return count;
        }
        if(map.containsKey(count)){
            return map.get(count);
        }else {
            int value=stepCount2(count-1,map)+stepCount2(count-2,map);
            map.put(count,value);
            return value;
        }
    }

//3.动态规划：时间复杂度n
private static int stepCount3(int count) {
        if (count<1){
            return 0;
        }
        if (count<=2){
            return count;
        }
        int left=1,right=2,temp=0;
        for (int i = 3; i <=count ; i++) {
            temp=left+right;
            left=right;
            right=temp;
        }
        return temp;
    }

注：以上解法出自微信公众号《程序员小灰》.