- 198. 打家劫舍 - 力扣（LeetCode）
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
// 0. Move index to 1-based
nums.insert(nums.begin(), 0);
// 1. Define f, initialize -oo
vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
f[0][0] = 0;
// 2. Loop over all states
for (int i = 1; i <= n; i++) {
// 3. Copy decision funcs
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + nums[i];
}
// 4. Return target
return max(f[n][0], f[n][1]);
}
};
- 213. 打家劫舍 II - 力扣（LeetCode）
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
nums.insert(nums.begin(), 0);
vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
// 将环强行断开
// 情况1：偷1号，n号不偷
f[1][0] = 0; // !!!偷1号时，也要初始化f[1][0]
f[1][1] = nums[1];
for (int i = 2; i <= n; i++) {
f[i][1] = f[i - 1][0] + nums[i];
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
}
int ans = f[n][0];
// 情况2：不偷1号，n号随意
f[1][0] = 0;
f[1][1] = -1e9; // !!!需要再重新赋初值
for (int i = 2; i <= n; i++) {
f[i][1] = f[i - 1][0] + nums[i];
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
}
return max(ans, max(f[n][0], f[n][1]));
}
};
- 72. 编辑距离 - 力扣（LeetCode）
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.length(), n = word2.length();
// 0. Move index to 1-based
word1 = " " + word1, word2 = " " + word2;
// 1. Define f, initialize -oo
vector<vector<int>> f(m + 1, vector<int>(n + 1, 1e9));
for (int i = 0; i <= m; i++) f[i][0] = i;
for (int j = 0; j <= n; j++) f[0][j] = j;
// 2. Loop over all states
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
// 3. Copy decision funcs
f[i][j] = min(min(f[i - 1][j] + 1, f[i][j - 1] + 1),
f[i - 1][j - 1] + (word1[i] != word2[j]));
// 4. Return target
return f[m][n];
}
};
- 416. 分割等和子集 - 力扣（LeetCode）
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for (int i = 0; i < n; i++) sum += nums[i];
if (sum % 2 == 1) return false;
// 0. Move index to 1-based
nums.insert(nums.begin(), 0);
// 1. Define f, initialize -oo
vector<int> f(sum / 2 + 1, false);
f[0] = true;
// 2. Loop over all states
for (int i = 1; i <= n; i++)
for (int j = sum / 2; j >= nums[i]; j--)
// 3. Copy decision funcs
f[j] |= f[j - nums[i]];
// 4. Return target
return f[sum / 2];
/*
// 1. Define f, initialize -oo
vector<vector<int>> f(n + 1, vector<int>(sum + 1, false));
f[0][0] = true;
// 2. Loop over all states
for (int i = 1; i <= n; i++)
for (int j = 0; j <= sum; j++) {
// 3. Copy decision funcs
// 此处相当于直接拷贝，所以优化思路：直接原地拷贝
f[i][j] = f[i - 1][j];
if (j >= nums[i])
f[i][j] = f[i - 1][j - nums[i]] || f[i - 1][j];
}
return f[n][sum / 2];
*/
}
};
-
518. 零钱兑换 II - 力扣（LeetCode）
力扣第29测试过不去
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
coins.insert(coins.begin(), 0);
vector<int> f(amount + 1, 0);
f[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = coins[i]; j <= amount; j++)
f[j] += f[j - coins[i]];
return f[amount];
}
};
