改了很多溢出的问题之后，发现最优时间也是1ms，而大部分人都是0ms，悲伤之余去看了下别人的解答……
只想说思路很重要。刚开始也想到了，后续的台阶步数是与之前的和有关系的，但是没仔细找……
好吧。就当复习了一下组合数的计算方法，以及溢出的应对办法/(ㄒoㄒ)/~~
题目
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?
My Ugly Code
1 public class Solution {
2 public int climbStairs(
int n) {
3 if(n<2
)
4 return 1
;
5 int one=0,two = n/2
;
6 long count = 0
;
7 if(n%2!=0
)
8 one = 1
;
9 //n可以用two个2和one个1表示出来
10 //two的范围0~two(p),则one=(two-p)*2
11 for(
int p=0;p<two+1;p++
){
12 count = count + myCalc(((two-p)*2+one),p);
//1的个数,2的个数
13 }
14 return (
int)count;
15 }
16 private long myCalc(
int a,
int b){
17 int sum = a+
b;
18 int less = (a>b)?
b:a;
19 // System.out.println("sum="+sum+",less="+less);
20 if(less==0
)
21 return 1
;
22 long retd = 1,ret = 1
;
23 while(less>0
){
24 if(sum%less==0
){
25 ret *= (sum/
less);
26 }
27 else{
28 retd *=
less;
29 ret *=
sum;
30 }
31 //约分公因数，避免溢出
32 if(retd%2==0 && ret%2==0
){
33 retd = retd/2
;
34 ret = ret/2
;
35 }
36 if(retd%3==0 && ret%3==0
){
37 retd = retd/3
;
38 ret = ret/3
;
39 }
40 sum--
;
41 less--
;
42 }
43 // System.out.println(ret+"/"+retd);
44 return ret/
retd;
45 }
46 }
Others Genius Code
1 public class Solution {
2
3 public int climbStairs(
int n) {
4 if(n == 0 || n == 1 || n == 2){
return n;}
5 int[] mem =
new int[n];
6 mem[0] = 1
;
7 mem[1] = 2
;
8 for(
int i = 2; i < n; i++
){
9 mem[i] = mem[i-1] + mem[i-2
];
10 }
11 return mem[n-1
];
12 }
转载于:https://www.cnblogs.com/annaivsu/p/5660064.html
