题目链接：1049. 最后一块石头的重量 II
思路
把石头分成重量尽量相同的两堆，这样就能保证最后一块石头的重量最小。转换为01背包问题，重量和价值都是stone。
①dp数组，dp[j]表示容量为j的背包可以装的最大价值为dp[j]
②递推公式，dp[j] = max(dp[j], dp[j - stone[i]] + stone[i])
③dp数组初始化，遍历stone数组，计算总重量，取一半为dp数组大小，值为0；或者根据题目可知最大重量为30*100=30000，取一半15000即可，值为0
④遍历顺序，一维dp数组，先物品，后背包，背包倒序遍历
⑤推导dp数组
代码
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
if (stones.size() == 1)
return stones[0];
int sum = 0;
// 计算总重量
for (int a : stones)
sum += a;
int target = sum / 2;
vector<int> dp(target + 1, 0);
// 先物品
for (int i = 0; i < stones.size(); i++) {
// 后背包
for (int j = target; j >= stones[i]; j--) {
// 01背包
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
// 分成两堆，一堆dp[target]，另一堆sum-dp[target]
return sum - dp[target] - dp[target];
}
};题目链接：494. 目标和
思路
数组中有若干数字，在每个数字前面放加号或者减号使得最后的结果为target，可以理解为组合问题，使用回溯算法。每次遇到数字都是两种选择，如果最后等于目标，方法种类做累加操作。这种方法的问题在于时间复杂度，每次都是两种选择，并且数组中有若干数字，时间复杂度呈指数增长。
既然有加减两种运算符，那就将数组分为两个子集，加法子集left，减法子集right，数组所有数字之和为sum，则sum = left + right，target = left - right，联立两式可得left = (sum+target)/2，如此只需要在数组中寻找若干数字，使其和等于left即可，剩下的就是减法子集。将问题转化成了01背包问题。
①dp数组，dp[j]表示装满容量为j的背包有dp[j]种方法
②递推公式，dp[j] += dp[j-nums[i]]，举例，left=5时，装满需要dp[5]，而dp[5]可以由dp[4]+dp[1]得到，以此类推
③dp数组初始化，dp[0] = 1，因为要进行累加操作，所以dp[0]取1
④遍历顺序，先物品，后背包，背包倒序遍历
⑤推导dp数组
代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 目标值的绝对值比数组中所有数字和还要大，肯定无解
if (abs(target) > sum)
return 0;
// 不能整除，说明如何构造都满足不了题目要求
if ((sum + target) % 2 == 1)
return 0;
int left = (sum + target) / 2; // 背包容量
vector<int> dp(left + 1, 0);
dp[0] = 1; // dp数组初始化
// 先物品
for (int i = 0; i < nums.size(); i++) {
// 后背包，倒序遍历
for (int j = left; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[left];
}
};题目链接：474.一和零
思路
01背包的思路，数组中由若干物品，重量有两个维度，0的个数，1的个数；背包的容量也有两个维度，0和1的容量，m和n，最后求的是背包最多可以装多少件物品。
重量及容量涉及两个维度，加上所求的物品数量，总共三个变量，所以使用二维dp数组。
①dp数组，dp[i][j]表示容量为i个0和j个0的背包最多可以装dp[i][j]件物品
②递推公式，dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1)，x表示当前物品0的个数，y表示当前物品1的个数
③dp数组初始化，dp[0][0]=0，容量都为0，装不了物品；dp数组中非0容量也初始化为0，这是因为在递推公式中涉及到max取最大值
④遍历顺序，先物品，后背包，背包倒序遍历
⑤推导dp数组
代码
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // dp数组及初始化
// 01背包
// 先物品
for (string str : strs) {
int x = 0; // 记录当前物品0的数量
int y = 0; // 记录当前物品1的数量
for (char a : str) {
if (a == '0')
x++;
else
y++;
}
// 后背包，这里有两个维度0和1，倒序遍历
for (int i = m; i >= x; i--) {
for (int j = n; j >= y; j--) {
dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j]);
}
}
}
return dp[m][n];
}
};总结
①01背包的基础知识已经理解了，但是如何将题目转换为01背包问题还需要熟练
②目前来说，将题目转换为01背包问题，主要是要找到背包与物品，然后确定每种物品只有一件
③01背包问题：装满背包的组合有多少种，最多能装多少件物品等
④dp数组含义以及递推公式的细节处理