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?

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      

解決方法1：

運用dynamic programing的思想，如果我們想計算共有n個台階的情況

分倆種情況：

（1）（n-1）的台階的總情況數 + 最後邁一步

（2）（n-2）的台階的總情況數 + 最後邁倆步

我們用dp[n]代表n個台階的情況，dp[n] = dp[n-1] + dp[n-2].以此類推。

代碼如下：

public static int climbStairs(int n) {
		if(n == 1)
			return 1;
		int[]dp = new int[n+1];
		dp[1] = 1;
		dp[2] = 2;
		for(int i = 3;i < n + 1;i++)
		{
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[n];
	}
           

解決方法2:從上邊的方法我們可以看出，dp是一個斐波那契數列。 F i b ( n ) = F i b ( n − 1 ) + F i b ( n − 2 ).

這樣就更簡單了我們直接計算到n的情況就行了，不需要額外的數組了。

代碼如下：

public static int climbStairs(int n)
	{
		if(n == 1)
			return 1;
		int first = 1;
		int second = 2;
		for(int i = 3;i <= n;i++)
		{
			int third = first + second;
			first = second;
			second = third;
		}
		return second;
	}
           

(文章基于LeetCode提供的解決方法，主要記錄自己的學習，如果有人看的話可以直接移步LeetCode看解決方法，也不知道有沒有會看到。。。)