Climbing Stairs 111

Question

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3

Solution

ways[i]表示到i有多少种方法。

初始化：ways[0]=1, ways[1]=1

状态函数：ways[i]=ways[i-1]+ways[i-2]，即到i的方法数为到i－1的方法数＋到i－2的方法数。

优化：动态数组。

代码如下：

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        if(n <= 1){
            return 1;
        }

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

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

        return ways[n%2];
    }
}