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?
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp = [1, 2]
if n < 2:
return dp[n-1]
for x in xrange(2,n):
dp.insert(x, dp[x-1] + dp[x-2])
return dp[n-1]
Solution:
O(n) runtime, O(1) space – Dynamic programming: This is a classic Dynamic Programming problem. Define:
f(n) = number of ways you can climb to the nth step. To reach to the nth step, you have only two choices:
-
Advance one step from the n – 1th step.
-
Advance two steps from the n – 2th step.
Therefore, f(n) = f(n – 1) + f(n – 2), which is the exact same recurrence formula defined
by the Fibonacci sequence (with different base cases, though). Set base cases f(1) = 1, f(2) = 2 and you are almost done.
Now, we could calculate f(n) easily by storing previous values in an one dimension array and work our way up to n. Heck, we can even optimize this further by storing just the previous two values.
public int climbStairs(int n) { int p = 1, q = 1;
for (int i = 2; i <= n; i++) {
int temp = q; q += p; p = temp;
}
return q; }
留言列表
