leetcode 70. 爬楼梯问题（多种方法总结）

爬楼梯问题有多种出现形式，有不固定最多可跨阶数（即最多可跨阶数为M，M作为方法参数）的，有固定每次最多可跨2阶的。接下来，我就对以上两种出线形势分别进行分析。

（一）固定每次最多跨越2阶，使用非递归方式实现：

1、问题描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

2、首先我们把 n<=5 的不同情况列出来：

1	2	3	4	5
1	2	3	5	8

综上我们可以看出，爬楼梯的方案数f(n) = f(n) + f(n-1)

3、我们用java代码实现以上思路：

class Solution {
    public int climbStairs(int n) {
        if(n==1||n==2){
			return n;
		}
		int f1 = 1;
		int f2 = 2;
		int temp;
		for(int i=3; i<=n; i++){
			temp = f2;
			f2 += f1;
			f1 = temp;
		}
		return f2;  
    }
}

4、运行结果：

leetcode 70. 爬楼梯问题（多种方法总结）

（二）使用递归方式实现

1、问题描述：

假设一个楼梯有 N 阶台阶，人每次最多可以跨 M 阶，求总共的爬楼梯方案数。

2、算法实现（java语言）：

private static int calculateCount(int ladder, int maxJump) {
	    int jump = 0;
	    if (ladder == 0) {
	        return 1;
	    }
	    if (ladder >= maxJump) {
	        // 剩下的楼梯大于最大可跳跃数
	        for (int i = 1; i <= maxJump; i++) {
	            jump += calculateCount(ladder - i, maxJump);	           
	        }
	    } else {
	        // 剩下的楼梯不足最大可跳跃数
	        jump = calculateCount(ladder, ladder);	        
	    }
	    return jump;
	}

（三）递归和非递归实现性能比较：

package test;

/**
 * 
 * @author FHY
 * 爬楼梯问题
 *
 */
public class DynamicTest {
	public static void main(String[] args) {
		//对递归和非递归实现两种方法进行性能比较：
		long start = System.currentTimeMillis();
		getNums(30);
		long end1 = System.currentTimeMillis();
		System.out.println("非递归实现："+(end1-start));
		
		calculateCount(30,2);
		long end2 = System.currentTimeMillis();
	    System.out.println("递归实现:"+(end2-end1));
	}
	
	private static int calculateCount(int ladder, int maxJump) {		
	    int jump = 0;
	    if (ladder == 0) {
	        return 1;
	    }
	    if (ladder >= maxJump) {
	        // 剩下的楼梯大于最大可跳跃数
	        for (int i = 1; i <= maxJump; i++) {
	            jump += calculateCount(ladder - i, maxJump);
	        }
	    } else {
	        // 剩下的楼梯不足最大可跳跃数
	        jump = calculateCount(ladder, ladder);
	    }	    
	    return jump;
	}

	public static int getNums(int n){
		if(n==1||n==2){
			return n;
		}
		int f1 = 1;
		int f2 = 2;
		int temp;
		for(int i=3; i<=n; i++){
			temp = f2;
			f2 += f1;
			f1 = temp;
		}		
		long end = System.currentTimeMillis();
		return f2;
	}
}

输出：

非递归实现：0
递归实现:14

可见，递归实现性能很差！

leetcode 70. 爬楼梯问题（多种方法总结）

相关推荐