动态规划学习总结

动态规划学习总结

普通的动态规划

首先我这边给出动态规划的做题规范

1. 找出dp[i]的定义是什么
2. 找出dp[i]的推导公式
3. 初始化一些参数

01背包

1. 二维数组表示01背包。这个很好理解

    public static void testweightbagproblem(int[] weight,int[] value,int bagsize){
        int dp_x = weight.length;// weight.length表示的是有几个物品对吗。weight+1是把0这个情况包含进去的
        int dp_y = bagsize+1;//y表示0-bagsize，也是把0这个情况包含进去了

        //dp[i][j]的意思是，从0~i的物品随便拿，背包容量为j，能拿到的最大的value值
        int[][] dp = new int[dp_x][dp_y];

        //初始值的赋予
        //当j = 0的时候，也就是当背包容量为0的时候，那你能拿到的value也是0
        for(int i = 0;i=weight[0])
                dp[0][j] = value[0];
        }

//        开始书写转移方程
        for(int i = 1;i= weight[i]){
                    int temp = dp[i-1][j-weight[i]] + value[i];
                    dp[i][j] = Math.max(dp[i-1][j],temp);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        for(int x = 0;x

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36

core point：
1. 抓住dp[i][j]的定义。表示 0~i号物品任选，背包容量为j的情况下，能够拿到价值最大的情况。
2. dp_x表示物品的多少，就是weight数组的宽度
3. dp_y表示背包容量。dy = bagsize+1。包含了容量为0的情况（为后续的转移方程做铺垫）
4. dp[i-1][j-weight[i]]的实际意义是0~i-1的物品任选，背包容量为j-weight[I]的情况下能选择的价值最大的情况。（为什么要用j-weight[i]，因为下一步就是weight[j]）
5. 转移方程dp[i][j] = max(dp[i-1][j]，dp[i-1][j-weight[i]]+value[i])

2. 一维数组表示01背包

    public static void testweightbagproblem(int[] weight,int[] value,int bagsize){
        int[] dp = new int[bagsize+1];//定义一维的 0 1背包
        dp[0] = 0;
        for(int i = 0;i=weight[i];j--){
                if(j>=weight[i]){
                    dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
                }
            }
            for (int x = 0;x

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

core point
1. 从二位数组表示01背包的转移方程中，我们可以看出dp[i]的情况只和dp[i-1]有关。那么直接使用一维数组，每次在dp[i-1]的基础上修改，表达01背包即可。（这个思想很重要）
2. for(int i = dp.length-1;j>weight[i];j–) 首先要从后往前遍历。从二维数组表示01背包就能看出更新是和dp[i-1]和dp[i][j-weight[i]]有关的。不能让前面的更新影响后面的，但是后面是不影响前面的，所以从后往前遍历。
3. j>=weight[i]，因为j是递减的，所以只要这么写就行，（只能这么写，因为这个防止了数组越界情况）。
4. 当前的dp[i]表示dp[i-1]体会这个思想好吧
5. 其实本质上就是那外层的i一次一次的刷dp[]，一次一次的更新dp[]。我们本质上是想获得A二维数组的最下面一行。那么现在直接给你最下面的一行。

其实可以手推一下，或者把一维数组表示01背包的情况每一次的迭代情况输出，你会发现迭代的情况其实就是二维数组

416.分割等和子集

捏妈，真的有人在第一眼看到这个题目就能往01背包上面转吗，太牛了吧，通过这道题，我发现01背包难的点在于

1. 把问题转换成01背包
2. 定义weight数组和value数组

    /**
        这题的难度还是在如何把这个问题转换成01背包的问题。
        1. 如果存在两个可分割的子集，那么这个集合的和一定是偶数
        2. 如果存在可分割的子集，那么一定存在这个子集的和为sum/2
        3. 如果定义一个容量为sum/2的背包，如果存在可分割子集，一定能填充满这个子集
        4. 我把nums[i]当成value，把sum/2当做容量。一定存在num[0]~num[i]之和等于sum/2（用最大去填补最大）
     */
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int sum = 0;
        for(int n:nums) sum+=n;
        if(sum % 2 !=0) return false;

        int target = sum / 2;
        int[] dp = new int[target+1];

        dp[0] = 0;//容量为0的bagpack能拿的价值为0
        for(int i = 0;i=nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
//            for(int x = 0;x