动态规划二
6/15
T198打家劫舍！
1、嗯对，我是一个专业的小偷Bushi
2、如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（不是一定要偷i-1房），然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
3、代码实际上很短：
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};
T139单词拆分
1、回溯法做过类似的题，递归要降低复杂度的话需要做记忆化递归，及：使用memory数组保存每次计算的以startIndex起始的计算结果，如果memory[startIndex]里已经被赋值了，直接用memory[startIndex]的结果
2、关键：先遍历背包，再遍历物品
3、动态规划代码：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); i++) { // 遍历背包
for (int j = 0; j < i; j++) { // 遍历物品
string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
if (wordSet.find(word) != wordSet.end() && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.size()];
}
};
4、递归代码：
class Solution {
private:
bool backtracking (const string& s,
const unordered_set<string>& wordSet,
vector<bool>& memory,
int startIndex) {
if (startIndex >= s.size()) {
return true;
}
// 如果memory[startIndex]不是初始值了，直接使用memory[startIndex]的结果
if (!memory[startIndex]) return memory[startIndex];
for (int i = startIndex; i < s.size(); i++) {
string word = s.substr(startIndex, i - startIndex + 1);
if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, memory, i + 1)) {
return true;
}
}
memory[startIndex] = false; // 记录以startIndex开始的子串是不可以被拆分的
return false;
}
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> memory(s.size(), 1); // -1 表示初始化状态
return backtracking(s, wordSet, memory, 0);
}
};
6/14
T279完全平方数
1、这一题的思路有些绕，击中本质可化解为：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，求凑满这个背包最少有多少物品
2、关键：dp[j]：和为j的完全平方数的最少数量为dp[j]
3、这一题代码随想录里的举例分析能很好理清思路：
4、代码如下：
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; i++) { // 遍历背包
for (int j = 1; j * j <= i; j++) { // 遍历物品
dp[i] = min(dp[i - j * j] + 1, dp[i]);
}
}
return dp[n];
}
};
T322零钱兑换
1、本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。重要：求组合数就是外层for循环遍历物品，内层for遍历背包。 求排列数就是外层for遍历背包，内层for循环遍历物品。
2、所有下标非零的元素都应该用最大值初始化
3、代码如下：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包
if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
}
}
}
if (dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};
6/11
T57爬楼梯（进阶版，卡码官网题目，力扣无）
题干：
1、这一题对比之前的爬楼问题，初始化时就要注意： 既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果
2、养成ACM竞赛格式的刷题习惯，未来面试时未必有所有库可以用
3、代码如下：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
while (cin >> n >> m) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) { // 遍历背包
for (int j = 1; j <= m; j++) { // 遍历物品
if (i - j >= 0) dp[i] += dp[i - j];
}
}
cout << dp[n] << endl;
}
}
T377组合问题四
1、又回到了经典的组合问题！神奇的是，背包逻辑可以极简解决
2、手搓语法复习：取址符号&以及多重指针谨慎处理
3、代码如下：
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int j = 0; j < nums.size(); j++) {
if (i - nums[j] >= 0 && dp[i] <= INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};
6/10
T518 零钱兑换二
1、完全背包的两个for循环的先后顺序都是可以的，但本题不行，因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行，而本题要求凑成总和的组合数，元素之间明确要求没有顺序。
2、C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。
3、代码如下：
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1; // 只有一种方式达到0
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包
if (dp[j] < INT_MAX - dp[j - coins[i]]) { //防止相加数据超int
dp[j] += dp[j - coins[i]];
}
}
}
return dp[amount]; // 返回组合数
}
};
T474 一和零
1、这题严重怀疑命名是在呼应01背包问题，相对简单
2、题干中的物品就是strs里的字符串，背包容量就是题目描述中的m和n
3、代码如下：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
for (string str : strs) { // 遍历物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
6/8
T494 目标和
1、这一题仍是变种的背包问题，有二种解法：动态规划，回溯法
2、一维动态规划代码如下：
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 ((target + sum) % 2 == 1) return 0; // 此时没有方案
int bagSize = (target + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
3、对比回溯法，可以发现节省了许多语法上的复杂度，且回溯法由于本质暴力会在时间复杂度上超时：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
}
// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (S > sum) return 0; // 此时没有方案
if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要格外小心数值溢出的问题
int bagSize = (S + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和
// 以下为回溯法代码
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 需要排序
backtracking(nums, bagSize, 0, 0);
return result.size();
}
};
T1049 最后一块石头的重量
1、确定dp数组以及下标的含义 dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。 相对于 01背包，本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] 。 “最多可以装的价值为 dp[j]” 等同于 “最多可以背的重量为dp[j]”
-
确定递推公式 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
-
dp数组如何初始化 既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。 因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。
题干要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。 当然也可以把石头遍历一遍，计算出石头总重量 然后除2，得到dp数组的大小。
因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。
4、代码如下：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 0);
int sum = 0;
for (int i = 0; i < stones.size(); i++) sum += stones[i];
int target = sum / 2;
for (int i = 0; i < stones.size(); i++) { // 遍历物品
for (int j = target; j >= stones[i]; j--) { // 遍历背包
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};