理解dynamic programming动态规划

何谓动态规划？

以菲波那切数列为例，

 int fib(int n ){

       if(n == 0 || n ==1){

            return 1;

 　　　 }else{

            return fib(n - 1) + fib(n - 2);

 　　　 }

7 }

该递归调用中，有大量重复子集，如图

在计算fib(5) 的时候，多次计算了fib(2)的值。那为何不在递归搜索的基础上，添加一个小笔记本进行记忆化：只在第一次fib(2)的时候计算结果，而下次再call fib(2)的时候，可以直接O(1)时间从记事本拿到该结果。

  public int fib(int n ){

         if( n == 0 || n == 1) return 1;

         int [] memo = new int[n + 1]; // 另开一个空间memo记录

         Arrays.fill(memo, -1);  //memo上初始值都为-1

         if(memo[n] == -1){  // 若该值没被记录过

            memo[n] =  fib(n-1) + fib (n-2); //计算并记录在memo中

         }

         return memo[n]; //否则，该值不等于defalut的-1 表示已被记录过，直接拿结果

     }

那么，也可以在一个数组中滚动计算出最终memo[n], 这就是DP

   public int fib(int n ){

         int [] memo = new int[n + 1];

         memo[0] = 1;

         memo[1] = 1;

         for(int i = 2; i <=n; i++){

             memo[i] = memo[i-1] + memo[i-2];

         }

         return memo[n];

     }

总结：实际上，它们都是递归问题。在很多情况下，用记忆化搜索解出来的答案通常都是能满足需求的。只是动态规划的整个代码会更简洁清晰。也有很多面试官把递归调用时使用记忆化搜索等同于动态规划（top down with memorization is already DP）。当然，条件相同时，动态规划肯定更优。因为记忆化搜索的递归调用中，递归调用需要额外开销。空间角度，使用递归调用需要占用系统的栈空间。

巴特西

理解dynamic programming动态规划

最新文章

热门文章