# 70. Climbing Stairs

## Approach 1: 2D DP

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int climbStairs(int n) { // dp[i] := # of distinct ways to climb to i-th stair vector dp(n + 1); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int climbStairs(int n) { // dp[i] := # of distinct ways to climb to i-th stair int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n]; } } 
 1 2 3 4 5 6 7 8 9 class Solution: def climbStairs(self, n: int) -> int: # dp[i] := # of distinct ways to climb to i-th stair dp = [1, 1] + [0] * (n - 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] 

## Approach 2: 1D DP

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public: int climbStairs(int n) { int prev1 = 1; // dp[i - 1] int prev2 = 1; // dp[i - 2] for (int i = 2; i <= n; ++i) { const int dp = prev1 + prev2; prev2 = prev1; prev1 = dp; } return prev1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int climbStairs(int n) { int prev1 = 1; // dp[i - 1] int prev2 = 1; // dp[i - 2] for (int i = 2; i <= n; ++i) { final int dp = prev1 + prev2; prev2 = prev1; prev1 = dp; } return prev1; } } 
  1 2 3 4 5 6 7 8 9 10 11 class Solution: def climbStairs(self, n: int) -> int: prev1 = 1 # dp[i - 1] prev2 = 1 # dp[i - 2] for _ in range(2, n + 1): dp = prev1 + prev2 prev2 = prev1 prev1 = dp return prev1