# ac solution code

• 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
}

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