算法（10）--动态规划

动态规划

        动态规划中每一个状态一定是由上一个状态推导出来，动态规划通过记录历史来推断出新的状态。

        动态规划五部曲：

                1、确定dp数组以及下标的含义；

                2、确定递推公式；

                3、初始化dp数组

                4、确定遍历顺序

                5、打印dp数组

01背包问题

        例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

        01背包代表物品的两个状态，0代表不取，1代表取；

        第一步：确定dp数组以及其下标的含义

              dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

        第二步：确定递推公式

          递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        dp[i][j]代表第0~i物品里取，放进容量j的背包

        dp[i-1][j]代表不取第i个物品时的最大价值，也就是前一行的dp数组数值

         dp[i - 1][j - weight[i]] + value[i]取第i个物品时的价值，dp[i - 1][j - weight[i]]代表在第0~（i-1）物品中的（j - weight[i]）的最大价值

        第三步：初始化dp数组

        当j==0时，代表背包容量为0，所以需要把dp[i][0]初始化为0

        当i==0时，代表物品0是否取的状态，那么很明显当 j < weight[0]的时候，dp[0][j] 应该是0，因为背包容量比编号0的物品重量还小；当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

其他值都是在这个初始值的状态推断出来的，所以其他值初始化什么值都行。

        第四步：确定遍历顺序

        从行（物品）开始遍历或者从列（背包）开始遍历都可以，因为我们推断出下一个状态都需要前一个状态的值，这两种遍历方法都可以得出来。

        第五步：打印dp数组

        最终的结果就是去右下角的数组值

        做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！

代码如下：

public static int bag01(int[] weight,int[] value,int bagSize){
        //dp数组
        int[][] dp = new int[weight.length][bagSize+1];
        //递推公式
        //初始化
        for(int j = 0;j<dp[0].length;j++){
            if(j>=weight[0]){
                dp[0][j] = value[0];
            }
        }
        //遍历顺序：先物品在背包
        for(int i = 1;i<weight.length;i++){
            for(int j = 1;j<dp[0].length;j++){
                if(j >= weight[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                 }
            }
        }
        return dp[weight.length-1][bagSize];
    }

01背包改进--滚动数组

        01背包是通过二维数组记录上一状态的数值，滚动数组是把二维数组压缩成一维数组；

        由下图可知，我们i==2的数值都是由i==1推断出来的，所以我们只用一维数组来记录上层数值是够用的；

        

操作步骤：初始化数组dp[j],这一步骤和上面的相同

        for(int j = 0;j<dp[0].length;j++){
            if(j>=weight[0]){
                dp[0][j] = value[0];
            }
        }

        遍历顺序是从后往前，因为确定后面的数值需要上一层数值

        举例：确定物品1时，dp[4]的值要么是直接继承原来15的值，要么是由物品1的价值+dp[4-物品1重量],所以可知使用一维数组接值的要点是遍历顺序需要从后往前。

代码如下：

public static int bag01(int[] weight,int[] value,int bagSize){
        //dp数组
        int[] dp = new int[bagSize+1];
        //递推公式
        //初始化
        for(int i = 0;i<dp.length;i++){
            if(i >= weight[0]) dp[i] = value[0];
        }
        //遍历顺序：先物品在背包
        for(int i = 1;i<weight.length;i++){
            for(int j = dp.length-1;j > 0;j--){
                if(j >= weight[i]){
                    dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
                }else{
                    dp[j] = dp[j];
                }
            }
        }
        return dp[dp.length-1];
 
    }

---------------------------------------------------------------------------------------------------------------------------------

本人是刷《代码随想录》这本书时记录一下自己的学习笔记