A backtrack way with cache to reduce time


  • 0
    U
    class Solution {
    var cache = [Int:Int]()
    
    func backtrack(remain: Int) -> Int {
        var count = 0
        
        if let cached = cache[remain] {
            return cached
        }
        
        if remain == 0 {
            return 1
        }
        
        if remain - 1 >= 0 {
            count += backtrack(remain - 1)
        }
        
        if remain - 2 >= 0 {
            count += backtrack(remain - 2)
        }
        
        cache[remain] = count
        
        return count
    }
    
    func climbStairs(n: Int) -> Int {
        return backtrack(n)
    }
    

    }

    Pretty straightforward ha.


Log in to reply
 

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