高级工程师面试常见算法问题--动态规划

问题：有n步台阶，一次只能上1步或者2步，走完有多少种办法

思考：
1.当n=0 或者 n=1时，f（0）=0；f（1）=1；
2.n=2时，f(2)可以是一次2步，或两次1步,所以f(2) = f(1) + f(0)
n=3时，到达f(3)的前一次的走法只能是从第一个台阶上踏2步上来，或者是第二个台阶一步走上来，所以f(3) = f(2) + f(1)
3.依此类推 f(n) = f(n-1) + f(n-2)

实现：

/**
* 算法-有n步台阶，一次只能上1步或2步，共有多少种走法
*/
public class DP {

   //递归----最简单，暴力穷举
   public static int recu(int n){
       if(n<=2){
           return n;
       }
       int result = recu(n-1) + recu(n-2);
       return result;
   }

   //迭代算法----最快
   public static int iter(int n){
       if(n<=2){
           return n;
       }
       int third =0,first =1,second=2;
       for(int i=3;i<n;i++){
           third = first+second;
           first = second;
           second = third;
       }
       return third;
   }

   //动态规划----计算过的结果不需要再次计算，空间换时间
   public static int[] DPResult = new int[100];
   public static int dp(int n){
       if(n<=2){
           DPResult[n] = n;
       }
       if(DPResult[n]>0){
           return DPResult[n];
       }else {

           DPResult[n] = dp(n-1)+dp(n-2);
           return DPResult[n];
       }

   }


   public static void main(String[] args) {
       long startTime = System.currentTimeMillis();    //获取开始时间
       int n = 40;//别超太多，整数会溢出
       int recuResult = recu(n);
       long endTime = System.currentTimeMillis();    //获取结束时间
       System.out.println("递归结果="+recuResult+"    程序运行时间：" + (endTime - startTime) + "ms");    //输出程序运行时间

startTime = System.currentTimeMillis();
       int iterResult = iter(n);
       endTime = System.currentTimeMillis();
       System.out.println("迭代结果="+iterResult+"    程序运行时间：" + (endTime - startTime) + "ms");    //输出程序运行时间

       startTime = System.currentTimeMillis();
       int dpResult = dp(n);
       endTime = System.currentTimeMillis();
       System.out.println("动态规划结果="+dpResult+"    程序运行时间：" + (endTime - startTime) + "ms");    //输出程序运行时间

   }

}

程序结果：

image.png

最后编辑于：2019.08.07 16:20:14