LeetCode[动态规划] - #7 Climbing Stairs

原题链接：#7 Climbing Stairs

 

问题：

你正在攀爬一把一共有n个台阶的梯子，每次可以爬一或二阶，爬到顶共有多少种不同的方式？

 

难度：简单

 

分析：

当梯子阶数为0时，有0种攀爬方式；当阶数为1时，则有一种攀爬方式。当阶数为2时，由于每次可以爬一阶或两阶，即从0阶处爬两阶到达顶部或由1阶处爬1阶到达顶处，共2种方式。n=3时同样，可以由1阶处爬两阶或由2阶处爬1阶到达。设对于i阶阶梯不同的攀爬方式为S(i)，可得递推公式为 S(i) = S(i-1) + S(i-2) (2≤i≤n) （看起来很眼熟 ;-)）

 

解决方案：

Java - 244ms

public int climbStairs(int n) {
        if(n==0||n==1||n==2){
            return n;
        }

        int[] ways = new int[n+1];
        ways[0] = 0;
        ways[1] = 1;
        ways[2] = 2;

        for(int i=3; i<=n; i++){
            ways[i] = ways[i-1] + ways[i-2];
        }

        return ways[n];
    }

 简单测试程序