Climbing Stairs

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?

Thoughts

典型的DP，注意处理好边角条件

Solution

class Solution:
    """
    @param n: An integer
    @return: An integer
    """
    def climbStairs(self, n):
        # write your code here
        if not n:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 2
        f = [0 for x in range(n+1)]
        f[1] = 1
        f[2] = 2
        for i in range(3, n + 1):
            f[i] = f[i-1] + f[i-2]

        return f[n]