LeetCode - 70 Climbing Stairs

作者 QIFAN 日期 2016-07-14
LeetCode - 70 Climbing Stairs

Difficulty:Easy

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?

思路

排列组合

在算排列组合的时候要记得中途的结果会不会超过int范围。但其实如果方法合适也不会超过。

代码

public class Solution {
public int climbStairs(int n) {
int twos = 0;
int ones = n;
int ways = 0;
while(ones>=0) {
ways += times((ones+twos), twos);
twos++;
ones = n - 2 * twos;
}
return ways;
}
// 计算排列组合
public int times(int n, int m) {
if(n<2*m) m = n - m;
if(m==0) return 1;
double sum = n;
for(int i=1; i<m; i++) {
sum = sum * (n-i) / (i+1);
}
return (int)sum;
}
}

动态规划 & 递归解法:@Jiaming

原题链接:https://leetcode.com/problems/climbing-stairs/