1049 最后一块石头的重量II

思路：将整个数组中的数分为两部分，并且让其尽量相等，就可以达到最后一块石头最小的目的。由此，可以将该问题转换为一个背包问题，背包容量为 sum/2，在这个容量下拿到最大体积的石头。

1. 定义 dp 数组
   dp[i] 表示 i 容量下可以容纳石头的最大重量。
2. 递推公式
   dp[i] = Math.max(dp[i], dp[i-stones[j]]+stones[j]);
3. 初始化
   全部初始化为 0 即可
4. 遍历顺序
   当使用一维 dp 时，外层是物品，内层是容量，并且内层是倒序遍历。

class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int i : stones) {
sum += i;
}
int target = sum >> 1;
//初始化dp数组
int[] dp = new int[target + 1];
for (int i = 0; i < stones.length; i++) {
//采用倒序
for (int j = target; j >= stones[i]; j--) {
//两种情况，要么放，要么不放
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - 2 * dp[target];
}
}

416 分割等和子集

思路：这个题目和上边基本一致，将数组分为两部分。

1. 定义 dp
   dp[i] 代表数组中元素能不能装满 i 容量
2. 递推公式
   dp[i] = dp[i] || dp[i-nums[j]]
3. 初始化
   需要初始化，如果不做初始化，后续就没有变化了，这和上边题目中的 0 不一样。

Arrays.fill(dp, false);
if (nums[0] < cap+1)
dp[nums[0]] = true;

4. 遍历顺序
   同上，一维数组时，物品在外，容量在内，并且容量需要倒序。

class Solution {
public boolean canPartition(int[] nums) {
int length = nums.length;
int sum = 0;
for (int num:nums)
sum += num;
if (sum%2 == 1)
return false;
int cap = sum/2;
boolean[] dp = new boolean[cap+1];
Arrays.fill(dp, false);
if (nums[0] < cap+1)
dp[nums[0]] = true;
for (int i=1;i<length;i++) {
for (int j=cap;j>0;j--) {
if (j>=nums[i])
dp[j] =dp[j-nums[i]] || dp[j];
}
}
return dp[cap];
}
}

最后

以上就是慈祥电话为你收集整理的【leetcode】背包问题 5/61049 最后一块石头的重量II416 分割等和子集的全部内容，希望文章能够帮你解决【leetcode】背包问题 5/61049 最后一块石头的重量II416 分割等和子集所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。