动态规划思想轻松理解（java）

      动态规划出现在很多算法题目里面，初学者入门并不容易，网上很多文章看了以后还是不是很理解什么的动态规划算法，就打算记录一下自己的笔记，用案例加详细说明的方式深入理解动态规划的核心思想。

      以lletcode198题目为例（抢金店），不熟悉题目的同学可以百度一下~这是一个典型的动态规划类题目。

     首先看非动态规划怎么实现：

     

1. public class Solution{
2. public int rob(int[] nums){
3. return slove(nums.length,nums);
4. }
5. public int slove(int idx,int[] nums){
6. int max = Math.max(nums[idx] slove(idx- 2,nums),solve(idx-1,nums));
7. return max;
8. }
9. }

     上面的代码是通常的暴力搜索解法，这个一定要理解。本质上暴力搜索都是递归问题。说到这里，大家可能会问，怎么还没提到动态规划呢？

     我们仔细看上面的代码，会发现时间复杂度很高，为什么呢？   因为有大量的重复计算！做如下分析：

               n  -> (n-2,n-3,n-4,......)         //n代表一开始抢第n家店，后面以此类推。。。

               n-1    ->(n-3,n-4,.........) 

    这里，大家会发现，红色划线部分的店会重复计算，我们用动态规划就是希望去除冗余计算，降低时间复杂度。

   怎么做呢？基本步骤如下：

          1）设计暴力算法，找到冗余

          2）  设计并存储状态（一维，二维，三维，甚至Map）

         3） 递归式（状态转移方程）

         4）自低向上计算最优解

    一般的动态规划算法都需要以上流程，乍一看，写的啥，看不懂是吧，下面以这个题目为例详细解读这几个步骤，第一个步骤上面代码已经完成了，下面看第二步：之说以会重复计算，是因为我们没有保存已经计算过的店家，所有我们用一个中间状态来保留计算过的店家，以此防止重复计算，完整代码如下：

          

       

public class Solution{

1. public static int[] result;//记录中间态
2. public int rob(int[] nums){

result = new int[num.length-1];

for(int i =0;i<num.length-1;i ){

result[i] = -1;//初始化为，-1表示没有计算过

1. }
2. return slove(nums.length,nums);
3. }
4. public int slove(int idx,int[] nums){

if(result[ids]>=0{

                    return result[idx];//大于0，表示该位置计算过了，直接返回，该行代码很关键

1. }
2. int max = Math.max(nums[idx] slove(idx- 2,nums),solve(idx-1,nums));
3. return max;
4. }
5. }

          以上代码中，红色部分为第二部。设计了一个中间状态，好好体会吧~

         下面看第三部代码：

max = Math.max(nums[idx] slove(idx- 2,nums),solve(idx-1,nums));

        状态转移方程就是一个递归式。

        到这里，应该理解了动态规划的核心啦，做一个小总结：

            1）思考过程为：原问题->子问题->原问题   的过程
            2） 去冗余，空间换时间

         

       

[java] view plaincopyprint?

1.