【LeetCode-面試演算法經典-Java實現】【073-Climbing Stairs(爬樓梯)】

【LeetCode-面試演算法經典-Java實現】【073-Climbing Stairs(爬樓梯)】

【073-Climbing Stairs(爬樓梯)】


【LeetCode-面試演算法經典-Java實現】【所有題目目錄索引】

原題

  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?

題目大意

  你正在爬一個樓梯,要走n步才能到達頂部,每次你可以走兩步或者一步,請問你有多少種不同的方法爬到頂部。

解題思路

  解法一:用組合數的思想求解,分下面的情況,沒有一次走兩個臺階的有C(0, n),只一次走兩個臺階C(1, n-1),只二次走兩個臺階,C(2, n-2),直到只有[n/2](向下取整)次走兩個臺階。其和就是所有的解法。
  解法二:使用分治法,對n個臺階,用一個陣列儲存其解,a[1] = 1,a[2] = 2, k >= 2,有a[k] = a[k-1] a[k-2].

程式碼實現

演算法實現類,解法一

public class Solution {
public int climbStairs(int n) {
if (n < 0) {
return 0;
} else {
int result = 0;
for (int i = 0; i <= n; i  , n--) {
result  = combination(i, n);
}
return result;
}
}
/**
* 求組合數
*
* @param sup 上標
* @param sub 下標
* @return 結果
*/
private int combination(int sup, int sub) {
if (sup > sub || sup < 0 || sub < 0) {
throw new RuntimeException("Error args");
}
if (sup == 0) {
return 1;
}
if (sup > sub / 2) {
sup = sub - sup;
}
long x = 1; // 分母的積
long y = 1; // 分子的積
long z;
for (int i = 1; i <= sup; i  ) {
x *= (sub - i   1);
y *= i;
z = gcd(x, y); // 找最大公約數
// 分子分母都縮小最大公約數倍
x /= z;
y /= z;
}
return (int) (x / y);
}
private int gcd(long min, long max) {
long tmp;
if (max < min) {
tmp = min;
min = max;
max = tmp;
}
while (max % min != 0) {
tmp = min;
min = max % min;
max = tmp;
}
return (int) min;
}
}

演算法實現類,解法二

public class Solution {
public int climbStairs(int n) {
int result = 0;
// 只有一階
if (n == 1) {
result = 1;
}
// 只有兩階
else if (n == 2) {
result = 2;
}
// 樓梯階數大於2
else if (n > 2) {
// 儲存所有的解法
int[] ways = new int[n];
ways[0] = 1;
ways[1] = 2;
for (int i = 2; i < ways.length; i  ) {
ways[i] = ways[i - 1]   ways[i - 2];
}
result = ways[ways.length - 1];
}
return result;
}
}

評測結果

  點選圖片,滑鼠不釋放,拖動一段位置,釋放後在新的視窗中檢視完整圖片。
解法一
這裡寫圖片描述

解法二
這裡寫圖片描述

特別說明

歡迎轉載,轉載請註明出處【http://blog.csdn.net/derrantcm/article/details/47247995