LeetCode 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?

X.DP

The person can reach n’th stair from either (n-1)’th stair or from (n-2)’th stair. Let the total number of ways to reach n’t stair be ‘ways(n)’. The value of ‘ways(n)’ can be written as following.

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

The nth stairs is from either n-1th the stair or the n-2th stair. 

http://www.cnblogs.com/springfor/p/3886576.html

假设梯子有n层，那么如何爬到第n层呢，因为每次只能怕1或2步，那么爬到第n层的方法要么是从第n-1层一步上来的，要不就是从n-2层2步上来的，所以递推公式非常容易的就得出了：

dp[n] = dp[n-1] + dp[n-2]

令an为n级楼梯的走法数，要到达第n级，可以从第n-1级或第n-2级到达，于是

an = an-1 + an-2

https://segmentfault.com/a/1190000003707400

    public int climbStairs(int n) {
        if(n==0) return 0;
        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];
    }

By taking one step, there are T(n−1) distinct ways to finish the remaining. And by taking two steps, there are T(n−2) distinct ways to finish the remaining. That is, a recursion relationship can be identified:

T(n)=T(n−1)+T(n−2).

This is exactly the definition of Fibonacci sequence.

public int climbStairs(int n) {

        int f1 = 1, f2 = 2;

        if (n == 1)

            return f1;

        if (n == 2)

            return f2;

        for (int i = 3; i <= n; i++) {

            int f3 = f1 + f2;

            f1 = f2;

            f2 = f3;

        }

        return f2;

    }

Another possible way is to leverage its matrix representation:

(Fn+1FnFnFn−1)=(1110)n+1.

可以转换成斐波那契数列进行解答
http://www.jiuzhang.com/solutions/climbing-stairs/

    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        int last = 1, lastlast = 1;
        int now = 0;
        for (int i = 2; i <= n; i++) {
            now = last + lastlast;
            lastlast = last;
            last = now;
        }
        return now;
    }

http://likesky3.iteye.com/blog/2200855

1.      // O(1)空间  
2.      public int climbStairs(int n) {  
3.         if (n <= 0)  
4.             return 0;  
5.         int[] dp = {1, 1, 1};  
6.         for (int i = 2; i <= n; i++) {  
7.             dp[2] = dp[1] + dp[0];  
8.             dp[0] = dp[1];  
9.             dp[1] = dp[2];  
10.         }  
11.         return dp[2];  
12.      } 

Code from http://my.oschina.net/u/811399/blog/141550
public class Solution {
    public int climbStairs(int n) {
        // Start typing your Java solution below
        // DO NOT write main()
    double s = Math.sqrt(5);
   return (int)Math.floor(1/s*( Math.pow(0.5+s/2,(double)n+1)-Math.pow(0.5-s/2,(double)
    }
}
X. Recursive Based DP
http://buttercola.blogspot.com/2014/09/leetcode-climbing-stairs.html

    public int climbStairs(int n) {

        if (n <= 1) {

            return 1;

        }

         

        int[] dp = new int[n + 1];

        return climbStairsHelper(0, n, dp);

    }

     

    private int climbStairsHelper(int cur, int n, int[] dp) {

        if (cur > n) {

            return 0;

        }

         

        if (cur == n) {

            return 1;

        }

         

        if (dp[cur] != 0) {

            return dp[cur];

        }

         

        dp[cur] = climbStairsHelper(cur + 1, n, dp) + climbStairsHelper(cur + 2, n, dp);

         

        return dp[cur];

    }

https://leetcode.com/discuss/42044/3-4-short-lines-in-every-language
public int climbStairs(int n) { int a = 1, b = 1; while (n-- > 0) a = (b += a) - a; return a; }

    public int climbStairs(int n) {
        if(n==1 || n==0) return 1;
        else return climbStairs(n-1) + climbStairs(n-2);
    }

    public int climbStairs(int n) {

        if (n <= 1) {

            return 1;

        }

         

        return climbStairsHelper(0, n);

    }

     

    private int climbStairsHelper(int cur, int n) {

        if (cur > n) {

            return 0;

        }

         

        if (cur == n) {

            return 1;

        }

         

        return climbStairsHelper(cur + 1, n) + climbStairsHelper(cur + 2, n);

    }

Triple Step: A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3
steps at a time. Implement a method to count how many possible ways the child can run up the
stairs.

The one tricky bit is defining the base case. If we have O steps to go (we're currently standing on the step),
a re there zero paths to that step or one path?
That is, what is countWays(0)? Is it 1 orO?
You could define it either way. There is no"right" answer here.
However, it's a lot easier to define it as 1. If you defined it as 0, then you would need some additional base
cases (or else you'd just wind up with a series of Os getting added).

int countWays(int n) {
        if (n < 0) {
                return 0;
        } else if (n ==0) {
                return 1;
        } else {
                return countWays(n-1) + countWays(n-2) + countWays(n-3);
        }
}

Memoization Solution
Typically we use a HashMap<Integer, Integer> for a cache. In this case, the keys will be exactly 1
through n. It's more compact to use an integer array.
int countWays(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return countWays(n, memo);
}

int countWays(int n, int[] memo) {
        if (n < 0) {
                return 0;
        } else if (n == 0) {
                return 1;
        } else if (memo[n] > -1) {
                return memo[n];
        } else {
                memo[n] = countWays(n - 1, memo)+ countWays(n - 2, memo)+
                          countWays ( n - 3, memo);
                return memo[n];
        }
}

Talk about overflow issue to your interviewer. He probably won't ask you to work around it
(although you could, with a Biginteger class). but it's nice to demonstrate that you think about these
issues.
https://www.dailycodingproblem.com/blog/staircase-problem/
Read full article from LeetCode - Climbing Stairs | Darren's Blog