Leetcode 70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

This is actually Fibonacci sequence. We can get it by DP.

Solution 1:

# T:O(n) S:O(n)
class Solution:
    # @param {integer} n
    # @return {integer}
    def climbStairs(self, n):
        dp = [0, 1] + [0]*n
        for i in xrange(2, n + 2):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n + 1]

Run Time: 36 ms

Solution 2:

# T:O(n) S:O(1)
class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        prev, current = 0, 1
        for i in xrange(n):
            prev, current = current, prev + current, 
        return current

Run Time: 40 ms