Leetcode: 70. Climbing Stairs
Naive Solution
- Primary idea: Recursion to calculate fifibonacci sequence
- Time Complexity: O(2^n), because at each stair there are two choices and there are total of n stairs.
- Space Complexity: O(n), because of recursive stack space.
func climbStairs(_ n: Int) -> Int {
fib(n + 1)
}
func fib(_ n: Int) -> Int {
if n <= 1 {
return n
}
return fib(n - 1) + fib(n - 2)
}
climbStairs(1) // 2
climbStairs(2) // 2
climbStairs(3) // 3
climbStairs(4) // 5Optimised Solution
- Primary idea: Dynamic Programming (Memoization): dp[i] = dp[i - 1] + dp[i - 2]
- Time Complexity: O(n), where n is the number of steps.
- Space Complexity: O(1), constant space
func climbStairs(_ n: Int) -> Int {
// Base case: if n is 0 or 1, return 1
if n <= 1 { return 1 }
// Create an array to store the number of ways to reach each step
var dp = [Int](repeating: 0, count: n + 1)
dp[0] = 1
dp[1] = 1
// Fill the dp array
for i in 2...n {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n] // The number of ways to reach step n
}
climbStairs(1) // 2
climbStairs(2) // 2
climbStairs(3) // 3
climbStairs(4) // 5