package com.fishercoder.solutions;

/**Leetcode 70: 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?*/
public class _70 {
    //classical dp problem
    public int climbStairs(int n) {
        if (n < 1) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        int[] dp = new int[n + 1];
        //the number of ways to reach step n could be calculated from n-1 and n-2
        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 void main(String... strings) {
        _70 test = new _70();
        System.out.println(test.climbStairs(6));
    }
}

@@ -36,20 +36,33 @@
 %0A/**
-Leetcode 70:
+%0A * 70. Climbing Stairs%0A%0A
  You
@@ -128,16 +128,17 @@
 e top.%0A%0A
+ 
 Each tim
@@ -229,11 +229,348 @@
 top?
+%0A%0A Note: Given n will be a positive integer.%0A%0A Example 1:%0A%0A Input: 2%0A Output:  2%0A Explanation:  There are two ways to climb to the top.%0A%0A 1. 1 step + 1 step%0A 2. 2 steps%0A%0A Example 2:%0A%0A Input: 3%0A Output:  3%0A Explanation:  There are three ways to climb to the top.%0A%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
@@ -584,16 +584,50 @@
 s _70 %7B%0A
+  public static class Solution1 %7B%0A
     //cl
@@ -683,26 +683,24 @@
  n) %7B%0A      
-  
 if (n %3C 1) %7B
@@ -696,28 +696,24 @@
 f (n %3C 1) %7B%0A
-    
         retu
@@ -724,27 +724,22 @@
 ;%0A      
-  %7D%0A       
+%7D else
  if (n %3C
@@ -748,28 +748,24 @@
 ) %7B%0A        
-    
 return n;%0A  
@@ -760,35 +760,40 @@
 return n;%0A      
-  %7D
+%7D else %7B
 %0A        int%5B%5D d
@@ -981,18 +981,16 @@
         
-  
 dp%5Bi%5D = 
@@ -1052,141 +1052,18 @@
     
-%7D%0A%0A    public static void main(String... strings) %7B%0A        _70 test = new _70();%0A        System.out.println(test.climbStairs(6));%0A  
+  %7D%0A    %7D%0A
   %7D%0A

refactor 70