leetcode70.Climbing Stairs

发表于 更新于 分类于 ，

题目要求

1
假设有n级台阶（n为正整数），每次可以爬一级台阶或两级台阶。问有多少种方法爬完n级台阶？

递归方法

最后一步可以是一级台阶，或者是两级台阶，一共两种情况。可通过递归获得n-1级台阶和n-2级台阶的和获得n级台阶的结果
台阶数量过高的话，性能会很差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @author rale
 * 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.
 */
public class ClimbingStairs {

    //递归    
    public int climbStairs(int n) {
        if(n<=1){
            return 1;
        }
        if(n%2==0){
            return (int) (Math.pow(climbStairs(n/2), 2)+Math.pow(climbStairs(n/2-1), 2));
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

非递归情况

为了提高性能，将递归转化为循环
可以将题目转换为n级台阶中有几步是爬了两级台阶，几步是爬了一级台阶
例如 3级台阶的的场景为 3个一步 或者 1个一步加1个两步
则n级台阶的场景为：
假设n级台阶中有a个两步，n-2*a个一步，则情况总数为C(n-a,a)
a的取值范围为[0,n/2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @author rale
 * 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.
 */
public class ClimbingStairs {
        public int climbStairs(int n){
        if(n<=1){
            return 1;
        }
        int countTwo = 1;
        int total = 1;
        while(countTwo*2<=n){
            //此处应设为long，防止值溢出
            long temp = 1;
            for(int i = n-countTwo, j = 1 ; j<=countTwo; i--,j++){
                temp = temp*i/j;
            }
            total += temp;
            countTwo++;
        }
        return total;
    }
}