Nice DP solution


  • 0
    S
    class Solution:
    # @param n, an integer
    # @return an integer
    def __init__(self):
        pass
    def climbStairs(self, n):
        debug = 1
        if n  < 2:
            return n
        numones = {}
        numtwos = {}
        dp = {}
        numones[1] = 1
        numtwos[1] = 0
        dp[1] = 1
        for i in range(2, n+1):
            numones[i] = numones[i-1] + numtwos[i-1]
            numtwos[i] = numones[i-1]
            dp[i] = numones[i] + numtwos[i]
    
        return dp[n]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.