动态规划之背包问题
01背包
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
416. 分割等和子集（能否能装满背包）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean canPartition(int[] nums) {
int len=nums.length;
int sum=0;
for(int n:nums){
sum+=n;
}
if(sum%2!=0) return false;
int bagSize=sum/2;
int[] dp=new int[bagSize+1];
dp[0]=0;
for(int i=0;i<len;i++){
for(int j=bagSize;j>=nums[i];j--){
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[bagSize]==bagSize;
}
}
|
494. 目标和（装满背包有多少种方法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
int len=nums.length;
for(int i=0;i<len;i++){
sum+=nums[i];
}
if(target>sum) return 0;
if((sum+target)%2!=0) return 0;
int bagSize=(sum+target)/2;
int[] dp=new int[bagSize+1];
dp[0]=1;
for(int i=0;i<len;i++){
for(int j=bagSize;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[bagSize];
}
}
|
完全背包
有N件物品和⼀个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯⼀不同的地方就是，每种物品有无限件。
322. 零钱兑换（满背包所有物品的最小个数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int coinChange(int[] coins, int amount) {
int max=Integer.MAX_VALUE;
int[] dp=new int[amount+1];
for(int i=0;i<=amount;i++){
dp[i]=max;
}
dp[0]=0;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
if(dp[j-coins[i]]!=max){
dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
}
}
}
return dp[amount]==max?-1:dp[amount];
}
}
|
518. 零钱兑换II（装满背包有几种方法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1];
dp[0]=1;
for(int i=0;i<coins.length;i++){
for(int j=1;j<=amount;j++){
if(j>=coins[i]){
dp[j]+=dp[j-coins[i]];
}
}
}
return dp[amount];
}
}
|
279. 完全平方数（满背包所有物品的最小个数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int numSquares(int n) {
int max=Integer.MAX_VALUE;
int[] dp=new int[n+1];
for(int i=0;i<=n;i++){
dp[i]=max;
}
dp[0]=0;
for(int i=1;i*i<=n;i++){
for(int j=i*i;j<=n;j++){
if(dp[j-i*i]!=max){
dp[j]=Math.min(dp[j],dp[j-i*i]+1);
}
}
}
return dp[n];
}
}
|
139. 单词拆分（能否装满背包）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len=s.length();
boolean[] valid=new boolean[len+1];
valid[0]=true;
for(int i=1;i<=len;i++){
for(int j=0;j<i;j++){
if(wordDict.contains(s.substring(j,i))&&valid[j]){
valid[i]=true;
break;
}
}
}
return valid[len];
}
}
|
背包递推公式
问能否装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
**问装满背包有几种方法：dp[j] += dp[j - nums[i]] **
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
遍历顺序
01背包
一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
完全背包
纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历；
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不⼀样了；
如果求组合数就是外层for循环遍历物品，内层for遍历背包；
如果求排列数就是外层for遍历背包，内层for循环遍历物品；
如果求最小数，那么两层for循环的先后顺序就无所谓了。
微信
支付宝