【070-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].
代码实现
算法实现类，解法一
{(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 结果*/(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;}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);}(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 {(int n) {int result = 0;// 只有一阶if (n == 1) {result = 1;}(n == 2) {result = 2;}(n > 2) {[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;}}评测结果
点击图片，鼠标不释放，拖动一段位置，释放后在新的窗口中查看完整图片。 解法一
解法二
特别说明欢迎转载，转载请注明出处【】
如果前世五百次眸回，才换来今生的擦肩而过。
