package com.fishercoder.solutions;

/**
 * 70. 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?

 Note: Given n will be a positive integer.

 Example 1:
 Input: 2
 Output:  2
 Explanation:  There are two ways to climb to the top.
 1. 1 step + 1 step
 2. 2 steps

 Example 2:
 Input: 3
 Output:  3
 Explanation:  There are three ways to climb to the top.
 1. 1 step + 1 step + 1 step
 2. 1 step + 2 steps
 3. 2 steps + 1 step

 */

public class _70 {
  public static class Solution1 {
    /**
     * O(n) time
     * O(n) space
     * */
    public int climbStairs(int n) {
      if (n == 1) {
        return n;
      }
      int[] dp = new int[n + 1];
      dp[1] = 1;
      dp[2] = 2;
      for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[n];
    }
  }

  public static class Solution2 {
    /**
     * O(n) time
     * O(1) space
     * */
    public int climbStairs(int n) {
      if (n == 1) {
        return n;
      }
      int stepOne = 1;
      int stepTwo = 2;
      for (int i = 3; i <= n; i++) {
        int tmp = stepTwo;
        stepTwo = stepOne + stepTwo;
        stepOne = tmp;
      }
      return stepTwo;
    }
  }
}

@@ -33,539 +33,8 @@
 s;%0A%0A
-/**%0A * 70. Climbing Stairs%0A%0A You are climbing a stair case. It takes n steps to reach to the top.%0A Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?%0A%0A Note: Given n will be a positive integer.%0A%0A Example 1:%0A Input: 2%0A Output:  2%0A Explanation:  There are two ways to climb to the top.%0A 1. 1 step + 1 step%0A 2. 2 steps%0A%0A Example 2:%0A Input: 3%0A Output:  3%0A Explanation:  There are three ways to climb to the top.%0A 1. 1 step + 1 step + 1 step%0A 2. 1 step + 2 steps%0A 3. 2 steps + 1 step%0A%0A */%0A%0A
 publ
@@ -48,16 +48,18 @@
 s _70 %7B%0A
+  
   public
@@ -84,28 +84,36 @@
 tion1 %7B%0A    
-/**%0A
+    /**%0A    
      * O(n) 
@@ -118,24 +118,28 @@
 ) time%0A     
+   
+ 
 * O(n) space
@@ -136,37 +136,43 @@
 O(n) space%0A     
-*
+   
  */%0A
+    
     public int c
@@ -189,32 +189,38 @@
 (int n) %7B%0A      
+   
+   
 if (n == 1) %7B%0A  
@@ -209,32 +209,40 @@
   if (n == 1) %7B%0A
+        
         return n
@@ -241,34 +241,46 @@
 return n;%0A      
-%7D%0A
+      %7D%0A      
       int%5B%5D dp =
@@ -296,16 +296,22 @@
 n + 1%5D;%0A
+      
       dp
@@ -325,16 +325,22 @@
 ;%0A      
+     
+ 
 dp%5B2%5D = 
@@ -338,24 +338,30 @@
  dp%5B2%5D = 2;%0A
+      
       for (i
@@ -393,16 +393,24 @@
         
+     
+   
 dp%5Bi%5D = 
@@ -434,32 +434,44 @@
 - 2%5D;%0A      
-%7D%0A
+      %7D%0A  
       
+    
 return dp%5Bn%5D
@@ -476,21 +476,29 @@
 n%5D;%0A
+    
     %7D%0A
+  
   %7D%0A%0A  
+ 
+ 
 publ
@@ -525,28 +525,36 @@
 tion2 %7B%0A    
-/**%0A
+    /**%0A    
      * O(n) 
@@ -559,24 +559,28 @@
 ) time%0A     
+  
+  
 * O(1) space
@@ -589,13 +589,19 @@
     
-*
+   
  */%0A
+    
     
@@ -634,24 +634,30 @@
  n) %7B%0A      
+  
+    
 if (n == 1) 
@@ -658,32 +658,40 @@
 == 1) %7B%0A        
+       
+ 
 return n;%0A      
@@ -690,24 +690,36 @@
 ;%0A      
-%7D%0A
+      %7D%0A    
       
+  
 int step
@@ -729,24 +729,30 @@
  = 1;%0A      
+    
+  
 int stepTwo 
@@ -758,24 +758,30 @@
  = 2;%0A      
+   
+   
 for (int i =
@@ -791,32 +791,40 @@
  i %3C= n; i++) %7B%0A
+        
         int tmp 
@@ -838,24 +838,32 @@
 wo;%0A        
+ 
+       
 stepTwo = st
@@ -883,24 +883,32 @@
 wo;%0A        
+    
+    
 stepOne = tm
@@ -910,16 +910,22 @@
  = tmp;%0A
+      
       %7D%0A
@@ -926,24 +926,30 @@
     %7D%0A      
+ 
+     
 return stepT
@@ -956,16 +956,22 @@
 wo;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 70