Massive Algorithms: 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?

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:

(F n + 1 F n F n F n - 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

// O(1)空间
public int climbStairs(int n) {
if (n <= 0)
return 0;
int[] dp = {1, 1, 1};
for (int i = 2; i <= n; i++) {
dp[2] = dp[1] + dp[0];
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
}

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

LeetCode 70 - Climbing Stairs

Labels

Popular Posts