贵有恒何必三更眠五更起最无益只怕一日曝十日寒
动态规划是一种解决复杂问题的方法，它可以将一个问题分解为若干个子问题，然后利用子问题的最优解来构造原问题的最优解。动态规划的核心思想是避免重复计算，即将已经求解过的子问题的结果保存起来，以便后续使用。
背包问题是一类经典的动态规划问题，它描述了一个背包有一定的承重上限，而有若干个物品，每个物品有自己的重量和价值，如何选择装入背包的物品，使得背包内物品的总价值最大。背包问题有很多变种，例如01背包、完全背包、多重背包等，它们都可以用动态规划的方法来求解。
本文将介绍动态规划背包问题的基本概念和思路，并以leetcode里的题目作为案例，给出JAVA实现的答案。本文将涵盖以下几种类型的背包问题：
leetcode上相应的练习题
给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例1：
输入：nums=[1,5,11,5]输出：true解释：数组可以分割成[1,5,5]和[11]。
示例2：
输入：nums=[1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。
这道题可以转化为一个0-1背包问题，即从数组中选取若干个数，使得它们的和等于数组总和的一半。
如果数组总和是奇数，则直接返回false。
如果是偶数，则定义一个二维数组dp[i][j]
二维数组dp[i][j]表示从前i个数中选取若干个数，使得它们的和不超过j的最大值。则状态转移方程为：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])
其中，dp[i-1][j]表示不选第i个数，dp[i-1][j-nums[i]]+nums[i]表示选第i个数。最后判断dp[n][sum/2]是否等于sum/2即可。
classSolution{publicbooleancanPartition(int[]nums){//数组总和intsum=0;for(intnum:nums){sum+=num;}//如果总和是奇数，则不能分割成两个相等的子集if(sum%2==1){returnfalse;}//数组长度intn=nums.length;//dp数组int[][]dp=newint[n+1][sum/2+1];//初始化第一行为0for(intj=0;j<=sum/2;j++){dp[0][j]=0;}//遍历物品for(inti=1;i<=n;i++){//遍历容量for(intj=0;j<=sum/2;j++){//不选第i个数dp[i][j]=dp[i-1][j];//如果容量大于等于第i个数，可以选择选或不选if(j>=nums[i-1]){dp[i][j]=Math.max(dp[i][j],dp[i-1][j-nums[i-1]]+nums[i-1]);}}}//判断是否能分割成两个相等的子集returndp[n][sum/2]==sum/2;}}复杂度
题目：
给你一个整数数组nums和一个整数target。向数组中的每个整数前添加'+'或'-'，然后串联起所有整数，可以构造一个表达式：
例如，nums=[2,1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。
输入：nums=[1,1,1,1,1],target=3输出：5解释：一共有5种方法让最终目标和为3。-1+1+1+1+1=3+1-1+1+1+1=3+1+1-1+1+1=3+1+1+1-1+1=3+1+1+1+1-1=3示例2：
请你找出并返回strs的最大子集的长度，该子集中最多有m个0和n个1。
如果x的所有元素也是y的元素，集合x是集合y的子集。
输入：strs=["10","0001","111001","1","0"],m=5,n=3输出：4解释：最多有5个0和3个1的最大子集是{"10","0001","1","0"}，因此答案是4。其他满足题意但较小的子集包括{"0001","1"}和{"10","1","0"}。{"111001"}不满足题意，因为它含4个1，大于n的值3。示例2：
和LeetCode322是类似的一道题
给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。
计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回0。
假设每一种面额的硬币有无限个。
题目数据保证结果符合32位带符号整数。
输入：amount=5,coins=[1,2,5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1
示例3：
输入：amount=10,coins=[10]输出：1
这道题可以转化为一个完全背包问题，即从coins数组中选取若干个数，使得它们的和等于amount。定义一个一维数组dp[j]表示容量为j的背包可以装入的硬币组合数。则状态转移方程为：
dp[j]=dp[j]+dp[j-coins[i]]
其中，dp[j]表示不选第i种硬币，dp[j-coins[i]]表示选第i种硬币。注意这里是加号，因为要求所有可能的组合数。最后返回dp[amount]即可。
空间复杂度：O(amount)，需要创建一个一维dp数组。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
你可以认为每种硬币的数量是无限的。
输入：coins=[1,2,5],amount=11输出：3解释：11=5+5+1
输入：coins=[2],amount=3输出：-1
输入：coins=[1],amount=0输出：0
这道题可以转化为一个多重背包问题，即从coins数组中选取若干个数，使得它们的和等于amount，且每种硬币有有限个。定义一个一维数组dp[j]表示容量为j的背包可以装入的最少硬币个数。则状态转移方程为：
dp[j]=min(dp[j],dp[j-coins[i]]+1)
其中，dp[j]表示不选第i种硬币，dp[j-coins[i]]+1表示选第i种硬币。注意这里是最小号，因为要求最少的硬币个数。最后判断dp[amount]是否等于初始值，如果是则返回-1，否则返回dp[amount]。
背包问题是一类常见的动态规划问题，它的核心思想是定义一个合适的状态表示和状态转移方程，然后根据问题的要求进行初始化和遍历。在解决背包问题时，需要注意以下几点：