Climbing Stairs

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?

思路: 经典的DP 问题, 状态转移方程T[n] = T[N – 1] + T[N – 2]

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        if (n == 2) return 2;
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];

    }
}

优化到space O(1), 可以用两个指针来模拟。

public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        int pre = 1;
        int cur = 2;
        for(int i = 2; i < n; i++) {
            int tmp = cur;
            cur = cur + pre;
            pre = tmp;
        }

        return cur;

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s