ac solution code


  • 0

    This is an excellent question to demonstrate how to solve DP issue based on memorization DFS solution.

    /*
         Solution1. DP - based on Memorization DFS. time = O(n); space = O(n)
         */
        func climbStairs2(_ n: Int) -> Int {
            // 1. DP defition: DP[i] - number of distinct ways to climb n steps
            var DP =  [Int](repeating: 0, count: n + 1)
            // 2. Base case
            DP[0] = 1
            // 3. Ieteration equation
            for i in 1 ..< n + 1 {
                DP[i] = DP[i-1]         // 1 step
                if i - 2 >= 0 {
                    DP[i] += DP[i-2]    // steps
                }
            }
            // 4. Result: DP[n]
            return DP[n]
        }
    
        /*
         Solution2. Memorization DFS. time = O(n); space = O(n)
         */
        fileprivate var map = [Int: Int]()
        func climbStairs(_ n: Int) -> Int {
            guard n > 0 else {return 1}
            if map.keys.contains(n) {// Memo
                return map[n]!
            }
            var res = 0
            if n - 1 >= 0 {// 1 step
                res += climbStairs(n-1)
            }
            if n - 2 >= 0 {// 2 steps
                res += climbStairs(n-2)
            }
            map[n] = res// Save Memo
            return res
        }
    

Log in to reply
 

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