[LintCode] Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3

Solution 1. Recursion.

f(n) = f(n - 1) + f(n - 2)

 1 //Recursive DFS traverse, TLE
 2 public class Solution {
 3     private int count = 0;
 4     public int climbStairs(int n) {
 5         dfs(0, 1, n);
 6         dfs(0, 2, n);
 7         return count;
 8     }
 9     private void dfs(int stair, int steps, int n){
10         int sum = stair + steps;
11         if(sum == n){
12             count++;
13             return;
14         }
15         else if(sum > n){
16             return;
17         }
18         dfs(sum, 1, n);
19         dfs(sum, 2, n);
20     }
21 }

Solution 2. Dynamic Programming

Overlapping subproblems -> DP

 1 //DP O(n) time, O(n) space 
 2 public class Solution {
 3     public int climbStairs(int n) {
 4         if(n <= 1){
 5             return 1; 
 6         }
 7         int[] f = new int[n + 1];
 8         f[0] = 1; f[1] = 1;
 9         for(int i = 2; i <= n; i++){
10             f[i] = f[i - 1] + f[i - 2];
11         }
12         return f[n];
13     }
14 }

 1 //DP O(n) time, O(1) space 
 2 public class Solution {
 3     public int climbStairs(int n) {
 4         if(n <= 1){
 5             return 1; 
 6         }
 7         int[] f = new int[2];
 8         f[0] = 1; f[1] = 1;
 9         for(int i = 2; i <= n; i++){
10             f[i % 2] = f[(i - 1) % 2] + f[(i - 2) % 2];
11         }
12         return f[n % 2];
13     }
14 }