算法：爬楼梯问题及几种解法

今天药忘吃喽~ 2021-10-13 21:20 279阅读 0赞

> 有n级楼梯，有2种爬法，1次1级，或1次2级，问，n级楼梯有多少种爬法？

### 一、递归求解 ###

当n < 0时，无解，当n = 1 时，f ( n ) = 1， 当n = 2时，有两种方法，一次1级爬2次，或一次2级，  
f （n） = 2。当 n > 2时，第一次跳一级还是两级，决定了后面剩下的台阶的跳法数目的不同：如果第一次只跳一级，则后面剩下的n-1级台阶的跳法数目为f(n-1)；如果第一次跳两级，则后面剩下的n-2级台阶的跳法数目为f(n-2)。所以，得出递归方程，f(n) = f(n-1) + f(n-2)。问题本质是斐波那契数列。

/**上台阶问题,递归求解**/
    	public static int jumpStepFibonacci(int n,int m) {
    		if(n<0) return -1;
    		if(n<=2) return n;
    		return jumpStepFibonacci(n-1, m)+jumpStepFibonacci(n-2, m);
    	}

public static void main(String[] args) {
    		
    		int start = (int) System.nanoTime();
    		
    		System.out.println(jumpStepFibonacci(10, 2));
        	int end = (int)System.nanoTime();
    		System.out.println("time:"+(end-start)+"ns");
    	}

### 二、迭代法 ###

迭代法和递归法相比，核心思想没有变，只是将递归方法变为迭代。

/**上台阶问题,迭代法**/
    	public static int jumpStepIter(int n,int m) {
    		if(n<0) return -1;
    		if(n<=2) return n;
    		int temp1 =1;
    		int temp2 =2;
    		int res = 0;
    		for(int i =3;i<=n;i++) {
    			res = temp1 + temp2;
    			temp1 = temp2;
    			temp2 = res;
    		}
    		return res;
    	}

### 三、动态规划 ###

/**上台阶问题，dp**/
    	public static int climbStairs(int n) {
    		if(n==0) return -1;
    		if(n==1) return 1;
    		int []dp = new int [n];
    		dp[0] =1;
    		dp[1] =2;
    		for(int i=0;i<n-2;i++) {
    			dp[i+2]=dp[i]+dp[i+1];
    		}
    		return dp[n-1];
    	}

### 四、备忘录模式 ###

摘自：https://blog.csdn.net/wu2304211/article/details/52717578

public static int dfs(int n, int[] array) {
            if (array[n] != 0) {
                return array[n];
            } else {
                array[n] = dfs(n - 1, array) + dfs(n - 2, array);
                return array[n];
            }
        }
    
        public static int fib03(int n) {
            if (n == 0) {
                return 1;
            }
            if (n == 1 || n == 2) {
                return n;
            } else {
                int[] array = new int[n + 1];
                array[1] = 1;
                array[2] = 2;
                return dfs(n, array);
            }
        }

### 总结 ###

public static void main(String[] args) {
    		
    		int n = 20,m=2;
    		
    		int start1 = (int) System.nanoTime();
    		System.out.println(jumpStepFibonacci(n, m));
    		int end1 = (int)System.nanoTime();
    		System.out.println("递归:"+(end1-start1)+"ns");
    		
    		int start2 = (int) System.nanoTime();
    		System.out.println(jumpStepIter(n, m));
    		int end2 = (int)System.nanoTime();
    		System.out.println("迭代:"+(end2-start2)+"ns");
    		
    		int start3 = (int) System.nanoTime();
    		System.out.println(fib03(n));
    		int end3 = (int)System.nanoTime();
    		System.out.println("数组:"+(end3-start3)+"ns");
    		
    		
    		int start5 = (int) System.nanoTime();
    		System.out.println(climbStairs(n));
    		int end5 = (int)System.nanoTime();
    		System.out.println("dp:"+(end5-start5)+"ns");
    	}

**测试结果：** n=20时，随机测了几次，明显看出，迭代法、备忘录模式、动态规划是一个数量级的，效率较递归高。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjQ0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjQ0_size_16_color_FFFFFF_t_70]: /images/20211013/61ff63a7b6314bdc9abf41447b51154a.png