[算法]n阶台阶，一次走一步或两步，有多少种走法？

快来打我* 2024-04-19 13:30 59阅读 0赞

*  问题

> 一个楼梯有n阶，  
> 每一次可以走一个台阶或者二个台阶  
> i请问总共有几种走法

package other;
    
    import org.junit.Test;
    
    import java.util.Scanner;
    
    /** * 一个楼梯有n阶， * 每一次可以走一个台阶或者二个台阶 * i请问总共有几种走法 * * @aothor cds * @create 2019/9/18 - 20:02 */
    public class StepInto { 
    
    	@Test
    	public void testStep() { 
    		/** * 方法自己调自己叫递归 * 优点： 大问题转小问题、减少代码量、代码精简、可读性好 * 缺点： 浪费空间、容易堆溢出 * */
    		long start = System.currentTimeMillis();
    		System.out.println( demo1(4));
    		long end = System.currentTimeMillis();
    		System.out.println(" 运行时间： " + (end -start));
    
    		/** * 利用自身变量不停换算出新值称为迭代 * 优点： 运行效率好，时间只因为循环次数的增加而增加、没有额外的空间开销 * 缺点： 代码不如递归整洁、可读性差！ */
    		long start2 = System.currentTimeMillis();
    		System.out.println( demo2(4));
    		long end2 = System.currentTimeMillis();
    		System.out.println("运行时间 " + (end2 -start2));
    	}
    
    	/** * 使用递归的方式 * @param n * @return */
    	public int demo1(int n){ 
    		if (n < 1){ 
    			throw new IllegalArgumentException("n should > 1");
    		}
    		if (n == 1 || n ==2){ 
    			return n;
    		}else{ 
    			return demo1(n-2) + demo1(n-1);
    		}
    	}
    
    	public int demo2(int n) { 
    		if (n < 1){ 
    			throw new IllegalArgumentException("n should > 1");
    		}
    		if (n == 1 || n ==2){ 
    			return n;
    		}else{ 
    			// 初始化走到第二阶台阶的走法有2种
    			int one = 2;
    			// 初始化走到第一阶台阶的走法有1种
    			int two = 1;
    			// 总走法
    			int sum = 0;
    			/** * f(1) = 1 * f(2) = 2 * f(3) = f(1) + f(2) * f(4) = f(3) + f(2) = [f(1) + f(2)] + f(2) * f(5) = f(3) + f(4) = [f(1) + f(2)] + [f(1) + f(2) + f(2)] * f(6) = f(4) + f(5) * f(n) = f(n-1) + f(n-2) */
    			for (int i = 3;i <= n; i++){ 
    				sum = one +  two;
    				two = one;
    				one  = sum;
    
    			}
    			return sum;
    		}
    
    	}
    
    
    
    
    }