力扣刷题-动态规划算法2：

目录

• 题目一：343. 整数拆分
• 题目二：96.不同的二叉搜索树
• 知识点1：0-1背包理论基础1
• 知识点2：0-1背包理论基础2
• • 2.1 第一类背包问题：容量为k背包，存放物品，使得价值最大
  • 2.2 第二类背包问题：容量为k背包，存放物品，装满有多少种可能性
  • 2.3 总结：
• 题目三：416. 分割等和子集
• 题目四：494. 目标和

题目一：343. 整数拆分

1. 题目说明
   
2. 求解步骤
   1）纯数学问题，尽可能得到更多的三
   2）把剩下的数再和若干个三的乘积相乘。
3. 代码展示

class Solution {
    public int integerBreak(int n) {
        //纯数学方法，尽可能多3，在数大于四的时候
        if(n<=3) return n-1;
        //
        int a=1;
        //尽可能多的三
        while(n>4){
            n=n-3;
            a=a*3;
        }
        //把所有的三再和剩下的数相乘
        return a*n;
    }
}

5. 补充说明

题目二：96.不同的二叉搜索树

1. 题目说明
   
2. 求解思路
   对于动规这类题目，首先是找到动规表达式的意义：
   1）dp[i]表示i个节点组成不同二叉搜索树的个数
   2）然后就去试一试，dp[0],dp[1],dp[2].dp[3]分别为多少，推导出表达是式子。
   3）dp[0]=1; dp[1]=1 ; dp[2] =2 ;dp[3] =dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0] 故公式就出来了
   4）dp[i]=dp[0]*dp[i-1]+dp[1]*dp[i-2]+dp[2]*dp[i-2]+…dp[i-1]*dp[0];
3. 求解步骤
   1)推测dp数组的含义
   2）推导dp数组的迭代式
   3）dp数组的初始化 *** 作
   4）dp数组的遍历方式
   5）拿一个案例测试一下
4. 代码展示

class Solution {
    public int numTrees(int n) {
        //1)特殊情况先处理
        if(n<=2) return n;
        //2)dp数组初始化
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            for(int j=0;j<=i-1;j++){
                dp[i]+=dp[j]*dp[i-1-j];
            }
        }
        return dp[n];
        
    }
}

5. 补充说明
   1）稿明白dp数组的意义；
   2）还有就是找规律是核心；可以通过一个个例子来推导公式。（不需要证明）

知识点1：0-1背包理论基础1

1. 首先需要明白dp数组的含义。dp [i] [j]：物体在0-1之间选取，最大背包重量为j时，这时最大的价值。
2. dp数组的迭代公式：dp[i][j]: 基于两种情况而来：
   （1）：dp[i][j]=dp[i-1][j],即虽然多放了一个物体i，但是i没有放进来
   （2）：dp[i][j]=dp[i-1][j-weight[i]]+value[i],把物体i放进来了，但是需要腾出weight[i]的重量，即小找dp[i-1][j-weight[i]]的大小。
   （3）：比较两者大小，看看需不需要放进来：dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]];
3. 进行初始化：在java中，如果数组没有赋值，默认为0.需要对dp[0][j]进行初值的赋予。
4. 遍历的方式：可以先遍历物体再遍历重量（先右后下）；可以先遍历重量再遍历物体（先下后右）

//0——1背包问题：先遍历物品，再遍历重量
public class beibao {
        public static void main(String[] args) {
            //都dp数组的定义和初始化（默认为0）
            int[] weight=new int[]{3,2,1};
            int[] value=new int[]{15,20,30};
            int[][] dp=new int[weight.length][5];
            for(int j=weight[0]; j<=4; j++){
                    dp[0][j]=value[0];
            }
            //遍历方式：先遍历物品，再遍历重量/先遍历重量，再遍历物体一样的。
            for(int i=1;i<weight.length;i++){
                for(int j=0;j<=4;j++){
                    if(j<weight[i]) {
                        dp[i][j]=dp[i-1][j];
                    }else{
                        dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                    }
                }
            }
            System.out.println(Arrays.deepToString(dp));
            System.out.println("result="+dp[weight.length-1][4]);
        }
}

//0——1背包问题：先遍历重量，再遍历物品
public class beibao1 {
    public static void main(String[] args) {
        //都dp数组的定义和初始化（默认为0）
        int[] weight = new int[]{1, 3, 4};
        int[] value = new int[]{15, 20, 30};
        int maxweight = 4;
        int[] dp = new int[maxweight + 1];
        //初始化一维数组：
        for (int i = 0; i <= maxweight; i++) {
            if (i < weight[0]) {
                dp[i] = 0;
            } else {
                dp[i] = value[0];
            }
        }
        System.out.println("dp=" + Arrays.toString(dp));
        //进行遍历循环:先遍历物体，再遍历重量(这个顺序不能乱；可以从头开始遍历，前提是第一行需要初始化
        int num = weight.length - 1;
        for (int i = 1; i < weight.length; i++) {
            for (int j = weight[i]; j <= maxweight; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
            System.out.println("dp=" + Arrays.toString(dp));
        }
    }
}

知识点2：0-1背包理论基础2

我们经过迭代过程可以发现，当物体进行变更的时候，只是在前一行的基础上修改了一点点内容，这样，我们可以用一个一维数组表示。

2.1 第一类背包问题：容量为k背包，存放物品，使得价值最大

1. 首先需要明白dp数组的含义：dp [j]：最大背包重量为j时，这时最大的价值
2. dp数组的迭代公式：
   (1): 比较两者大小，看看需不需要放进来：dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i])
3. 进行初始化:使用默认初始化即可
4. 遍历方式：
   （1）：先物体再重量，因为是倒序，如果先重量后物体，那么背包每一个时刻只有一个值。
   （2）：在重量遍历的时候，从后先前，这样能够使得第一行满足条件，不用初始化第一行
   （3）：在遍历重量的时候，重量至少要大于等于当前物体的重量，不然就不变，都不需要比较大小。

public class beibao2 {
    public static void main(String[] args) {
        //定义dp数组，并初始化（默认为0，自动初始化）
        int[] weight = new int[]{1, 3, 4};
        int[] value = new int[]{15, 20, 30};
        int maxweight = 4;
        int[] dp = new int[maxweight + 1];
        
        for (int i = 0; i < weight.length; i++) {
            for (int j = maxweight; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
            System.out.println("dp=" + Arrays.toString(dp));
        }
    }
}

2.2 第二类背包问题：容量为k背包，存放物品，装满有多少种可能性

//背包的第二类问题
public class beibao3 {
    public static void main(String[] args) {
        int[] nums=new int[]{1,1,1,1,1};
        int weight=4;
        //初始化数组：
        int[] dp=new int[weight+1];
        dp[0]=1;
        //进行遍历迭代
        for(int i:nums){
            for(int j=weight;j>=i;j--){
                dp[j]+=dp[j-i];  //用到了i或者不用i
            }
        }
        System.out.println("result="+dp[weight]);
    }
}

2.3 总结：

1. 第一类01背包问题：
   1）问题描述：若干个物品，每个物品有对应的重量和价值，当背包大小固定为K时，如何装存物品，使得背包中物品的价值最大？
   2）求解方法：
   （1）：用一维dp数组：使用默认初值0；双层遍历，先正序遍历物品，再逆序遍历重量
   （2）：用二维dp数组：第一行初值赋予，双层遍历：物品和重量不分先后遍历，正序和逆序都可以。
2. 第二类01背包问题：
   1）问题描述：容量为k背包，存放物品，装满有多少种可能性？
   2）求解方法：
   （1）：用一维dp数组：dp[0]=1；双层遍历，先正序遍历物品，再逆序遍历重量,迭代方法为累加。

题目三：416. 分割等和子集

1. 题目说明
   
2. 求解步骤
   把该问题转变为一个背包问题。（每个物体只能取一次）
3. 代码展示

class Solution {
    public boolean canPartition(int[] nums) {
        //核心思路：分割为两个，那么每个的大小就是总和的一半；
        //可以用01背包问题，在容量为总和一半的时候，装入更大的value值等于总和一半。
        //dp数组进行初始化
        int sum=0;
        for(int i:nums){
            sum+=i;
        }
        if(sum%2==1) return false;
        int[] dp=new int[sum/2+1];

        //01背包问题
        for(int i=0;i<nums.length;i++){
            for(int j=sum/2; j>=nums[i]; j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[sum/2]==sum/2) return true;
        return false;

    }
}

题目四：494. 目标和

1. 题目说明
   

2. 求解步骤
   1）把问题转化为第二种类型的背包问题：对于若干个物品，有多少种存储方式，能够刚好装满容量为k的背包、
   2）P=abs((target+sum)/2) :问题的转换

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //01背包问题另一种：放入一定的数，求使得背包满了的存放种数
        //首先获得需要搜寻的背包大小
        int num=0;
        for(int i: nums)  num+=i;
        if((target+num)%2==1) return 0;
        int p=(target+num)/2;
        if(p<0) p=-p;   //target可以为负数，由于值为均为正整数，我们需要进行变号

        int[] dp=new int[p+1];  //背包需要的容量
        //初始化dp数组值
        dp[0]=1;
        //进行遍历寻值[从后向前,累加,这个思想非常重要]：数i放进去和不放进去，两种可能性，需要累加
        for(int i:nums){
            for(int j=p;j>=i;j--){
                dp[j]+=dp[j-i];
            }
        }
        return dp[p];
    }
}