🍺 动态规划
🍻 股票问题
🥂 🌸 121. 买卖股票的最佳时机 [数组] [股票] (动态规划)
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 第 i 天持有 j 只股票
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
dp = vector<vector<int>>(n, vector<int>(2));
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 状态转移
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
// 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// 第i天有股 = 第i-1天有股 / 第一次买入
dp[i][1] = max(dp[i - 1][1], - prices[i]);
}
}
return dp[n - 1][0];
}
};
🥂 🌸 122. 买卖股票的最佳时机Ⅱ [数组] [股票] (动态规划)
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 第 i 天持有 j 只股票的利润
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
dp = vector<vector<int>>(n, vector<int>(2));
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 状态转移
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
// 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// 第i天有股 = 第i-1天有股 / 第i-1天无股, 并买入
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
}
return dp[n - 1][0];
}
};
🥂 🌸 123. 买卖股票的最佳时机Ⅲ [数组] [股票] (动态规划)
class Solution {
private:
vector<vector<vector<int>>> dp; // dp[i][k][j]: 第 i 天交易 k 次持有 j 股的收益
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int K = 2; // 可以交易的次数
dp = vector<vector<vector<int>>>(n, vector<vector<int>>(K + 1, vector<int>(2)));
// base case
for (int k = 0; k <= K; ++k) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
}
for (int i = 1; i < n; ++i) {
dp[i][0][0] = 0;
dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);
}
// 状态转移
for (int i = 1; i < n; ++i) {
for (int k = 1; k <= K; ++k) {
// 今天完成k笔交易无股 = 昨天完成k笔交易无股啥也没干 / 昨天完成k-1笔有股且卖了只股票
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k - 1][1] + prices[i]);
// 今天完成k笔交易有股 = 昨天完成k笔交易有股啥也没干 / 昨天完成k笔无股今天买了只股票
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
}
}
return dp[n - 1][K][0];
}
};
🥂 🌸 188. 买卖股票的最佳时机Ⅳ [数组] [股票] (动态规划)
class Solution {
private:
vector<vector<vector<int>>> dp; // dp[i][k][j]: 第 i 天交易 k 次持有 j 股的收益
public:
int maxProfit(int K, vector<int>& prices) {
int n = prices.size();
dp = vector<vector<vector<int>>>(n, vector<vector<int>>(K + 1, vector<int>(2)));
// base case
for (int i = 0; i <= K; ++i) {
dp[0][i][0] = 0;
dp[0][i][1] = -prices[0];
}
for (int i = 1; i < n; ++i) {
dp[i][0][0] = 0;
dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);
}
// 状态转移
for (int i = 1; i < n; ++i) {
for (int k = 1; k <= K; ++k) {
// 今天完成k笔交易无股 = 昨天完成k笔交易无股啥也没干 / 昨天完成k-1笔有股且卖了只股票
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k - 1][1] + prices[i]);
// 今天完成k笔交易有股 = 昨天完成k笔交易有股啥也没干 / 昨天完成k笔无股今天买了只股票
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
}
}
return dp[n - 1][K][0];
}
};
🥂 🌸 309. 买卖股票的最佳时机含冷冻期 [数组] [股票] (动态规划)
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 第 i 天持有 j 只股票的利润
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
dp = vector<vector<int>>(n, vector<int>(2));
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
if (n > 1) {
dp[1][0] = max(dp[0][0], dp[0][1] + prices[1]);
// 前一天有股票 / 今天刚买
dp[1][1] = max(dp[0][1], -prices[1]);
}
// 状态转移
for (int i = 2; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
// 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// 第i天有股 = 第i-1天有股 / 第i-1天无股, 并买入
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
}
}
return dp[n - 1][0];
}
};
🥂 🌸 714. 买卖股票的最佳时机含手续费 [数组] [股票] (动态规划)
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 第 i 天持有 j 只股票的利润
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
dp = vector<vector<int>>(n, vector<int>(2));
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 状态转移
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
// 第i天无股 = 第i-1天无股/ 第i-1天有股, 并卖出, 但需要手续费
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
// 第i天有股 = 第i-1天有股 / 第i-1天无股, 并买入
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
}
return dp[n - 1][0];
}
};
🍻 打家劫舍
🥂 🌸 198. 打家劫舍 [数组] [打劫] (动态规划)
class Solution {
private:
vector<int> dp; // dp[i]: 抢到第 i 家的最大金额
public:
int rob(vector<int>& nums) {
int n = nums.size();
dp = vector<int>(n, 0);
// base case
dp[0] = nums[0];
if (n > 0) {
dp[1] = max(dp[0], nums[1]);
}
// 状态转移
for (int i = 2; i < n; ++i) {
// 抢上一家, 还是不抢上一家
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
};
🥂 🌸 213. 打家劫舍Ⅱ [数组] [打劫] (动态规划)
class Solution {
private:
vector<int> dp1, dp2; // dp[i]: 抢到第 i 家的最大金额
public:
int rob(vector<int>& nums) {
int n = nums.size();
// 终止条件
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
dp1 = vector<int>(n - 1, 0);
dp2 = vector<int>(n - 1, 0);
// base case
dp1[0] = nums[0];
dp1[1] = max(dp1[0], nums[1]);
// base case
dp2[0] = nums[1];
dp2[1] = max(dp2[0], nums[2]);
// 状态转移 [0 1 2 3 4] -> [0 1 2 3]
for (int i = 2; i < n - 1; ++i) {
// 抢上一家, 还是不抢上一家
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
}
// 状态转移 [0 1 2 3 4] -> [1 2 3 4]
for (int i = 2; i < n - 1; ++i) {
// 抢上一家, 还是不抢上一家
dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
}
return max(dp1[n - 2], dp2[n - 2]);
}
};
🥂 🌸 337. 打家劫舍III [数组] [打劫] (动态规划) (递归)
class Solution {
private:
unordered_map<TreeNode*, int> dp; // 抢到每个节点时的最大金额
public:
int rob(TreeNode* root) {
return traverse(root);
}
int traverse(TreeNode* root) {
if (root == nullptr) return 0;
// 备忘录有记, 返回金额
if (dp.count(root)) return dp[root];
// 做选择, 抢
int q1 = root->val;
if (root->left != nullptr) {
q1 += traverse(root->left->left) + traverse(root->left->right);
}
if (root->right != nullptr) {
q1 += traverse(root->right->left) + traverse(root->right->right);
}
// 做选择, 不抢
int q2 = 0;
q2 += traverse(root->left) + traverse(root->right);
// 更新 dp
dp[root] = max(q1, q2);
return dp[root];
}
};
🍻 背包问题
🥂 🌸 322. 零钱兑换 [数组] [背包] (动态规划)
class Solution {
private:
vector<vector<int>> dp; // 前 i 硬币凑齐 j 需要的最少硬币数
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
int n = coins.size();
dp = vector<vector<int>>(n + 1, vector<int>(amount + 1, INT_MAX - 1));
// base case
dp[0][0] = 0;
// 状态转移
for (int i = 1; i <= n; ++i) {
int cur = coins[i - 1];
for (int j = 0; j <= amount; ++j) {
if (cur <= j) {
// 前 i-1 个硬币凑成 j / 前 i 个硬币凑成 j-cur
dp[i][j] = min(dp[i - 1][j], dp[i][j - cur] + 1);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][amount] == INT_MAX - 1 ? -1 : dp[n][amount];
}
};
🥂 🌸 416. 分隔等和子集 [数组] [背包] (动态规划)
// 容量为 n 的背包, 是否可以装满 sum/2 的物品
class Solution {
private:
vector<vector<bool>> dp; // dp[i][j]: 前 i 个数是否可以装满 j
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;
int target = sum / 2;
dp = vector<vector<bool>>(n + 1, vector<bool>(target + 1, false));
// BASE CASE
for (int i = 0; i <= n; ++i) {
dp[i][0] = true;
}
// 状态转移方程
for (int i = 1; i <= n; ++i) {
int cur = nums[i - 1];
for (int j = 1; j <= target; ++j) {
if (cur == j) { // 只用第 i 个数就可以凑齐
dp[i][j] = true;
} else if (cur > j) { // 看前 i-1 个是否可以凑齐
dp[i][j] = dp[i - 1][j];
} else if (cur < j) { // 前 i-1 个数可以凑齐或凑到 j-nums[i]
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - cur];
}
}
}
return dp[n][target];
}
};
🥂 🌸 474. 一和零 [字符数组] [背包] (动态规划)
// 给定两个个容量为 m, n 的 0 1 背包, 看能装下多少个包含 0 1 的字符串
class Solution {
private:
vector<vector<vector<int>>> dp; // dp[i][j][k] 代表前 i 个 str 中可以放 j 个 0 k 个 1 的字符串数
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
dp = vector<vector<vector<int>>>(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
// BASE CASE
// dp[0][...][...] = 0;
// 状态转移方程, 状态: 选不选第 i 个字符串
// 选, dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - c0][k - c1])
// 不选, dp[i][j][k] = dp[i - 1][j][k]
for (int i = 1; i <= len; ++i) {
pair<int, int> getZO = count(strs[i - 1]);
int zeros = getZO.first, ones = getZO.second;
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= n; ++k) {
if (zeros <= j && ones <= k) {
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1);
} else {
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
}
return dp[len][m][n];
}
pair<int, int> count(string& str) {
int zeros = 0, ones = 0;
for (auto ch : str) {
if (ch == '0') {
zeros++;
} else {
ones++;
}
}
return make_pair(zeros, ones);
}
};
🥂 🌸 494. 目标和 [数组] [背包] (动态规划)
// 给两个背包, 一个背包里装正数, 一个装负数, 让和为 target
// 那么等价于让正背包里刚好凑满 (all + target) / 2
class Solution {
private:
vector<int> dp; // dp[i][j]: 从前 i 个数字中可以组合成 j 的方案个数
public:
int findTargetSumWays(vector<int>& nums, int target) {
// BASE CASE
int n = nums.size();
// 现在有两个背包, 一个装正数, 一个装负数
int total = 0;
for (int i = 0; i < n; ++i) {
total += nums[i];
}
if (abs(target) > total) return 0; // 目标太大了, 不可能凑到
if ((total + target) % 2 == 1) return 0; // pos 不为整数
int pos = (total + target) / 2;
dp = vector<int>(pos + 1, 0);
dp[0] = 1;
// 状态转移方程
// dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]] 算上最后一个数/ 不算最后一个数
for (int i = 1; i <= n; ++i) {
int cur = nums[i - 1];
for (int j = pos; j >= 0; --j) {
if (cur <= j) { // 可以选或不选
dp[j] = dp[j] + dp[j - cur];
}
}
}
return dp[pos];
}
};
🥂 🌸 518. 零钱兑换Ⅱ [数组] [背包] (动态规划)
// 给定一个容量为 amount 的背包, 和一堆硬币, 凑满的方法有多少种
class Solution {
private:
vector<vector<int>> dp; // dp[i][j] 前 i 个货币凑齐 j 的方案数
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
dp = vector<vector<int>>(n + 1, vector<int>(amount + 1, 0));
// BASE CASE
dp[0][0] = 1;
// 状态转移方程
for (int i = 1; i <= n; ++i) {
int coin = coins[i - 1]; // 当前硬币, 选不选
for (int j = 0; j <= amount; ++j) {
if (coin <= j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - coin]; // 不重复使用 coin/ 重复使用 coin
} else {
dp[i][j] = dp[i - 1][j]; // 不重复使用 coin
}
}
}
return dp[n][amount];
}
};
🥂 🌸 1049. 最后一块石头的重量 [数组] [背包] (动态规划)
// 分成两堆石头, 正的, 负的
// sum = heap1 + heap2, heap1 < heap2
// 求 heap1 - heap2 的最小值 -> heap2 的最大值, 且 heap2 <= sum / 2
// 给一个容量为 sum / 2 的背包, 看最多能装多少石头
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]:前 i 石头装进 target 容量背包的最大石头量
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size(); // 石头总量
int sum = 0;
for (auto& stone : stones) {
sum += stone;
}
dp = vector<vector<int>>(n + 1, vector<int>(sum / 2 + 1, 0));
// BASE CASE
// dp[0][...] = 0;
// 状态转移方程
// 如果第 i 块石头装不下 dp[i][j] = dp[i - 1][j]
// 如果第 i 块石头装得下 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i] + nums[i]])
for (int i = 1; i <= n; ++i) {
int stone = stones[i - 1];
for (int j = 0; j <= sum / 2; ++j) {
if (stone <= j) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stone] + stone);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return sum - 2 * dp[n][sum / 2];
}
};
🍻 编辑距离
🥂 🌸 72. 编辑距离 [字符串] [编辑距离] (动态规划)
// 定义 dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的编辑距离
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的编辑距离
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
// base case
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
// 状态转移
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 插入 or 删除 or 替换
// 如已知 i 与 j-1 相同 -> 那么让 i 与 j 相同则需添加一个 s1[i+1] = s2[j], 操作次数 +1
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[m][n];
}
};
🥂 🌸 583. 两个字符串的删除操作 [字符串] [编辑距离] (动态规划)
// 定义: dp[i][j]: 使 s1[0...i] s2[0...j] 相同的最少删除次数
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 使 s1[0...i] s2[0...j] 相同的最少删除次数
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
// base case
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
// 状态转移方程
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 删除 i or 删除 j
// 如已知 s1[0...i-1] == s2[0...j], 那么让 s1[0...i] == s2[0...j] 需要删除 s1[i], 操作 +1
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
}
};
🥂 🌸 1312. 让字符串成为回文串的最少插入次数 [字符串] [编辑距离] [回文] (动态规划)
// 定义 dp[i][j]: 对 s[i][j] 插入多少字符可以变为回文串
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 对 s[i...j] 插入多少个字符可以变为回文串
public:
int minInsertions(string s) {
int n = s.size();
dp = vector<vector<int>>(n, vector<int>(n, 0));
// BASE CASE
// for (int i = 0; i < n; ++i) dp[i][i] = 0;
// 状态转移方程
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len -1;
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
// 在 i 处插入 or 在 j 处插入
// 已知 s[i+1...j] 是回文, 让 s[i...j] 是回文需要插入一个字符, 操作 +1
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[0][n - 1];
}
};
🥂 🌸 712. 两个字符串的最小 ASCII 删除和 [字符串] [编辑和] (动态规划)
// 定义 dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的最小删除和
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 使 s1[0...i] 与 s2[0...j] 相等的最小删除和
public:
int minimumDeleteSum(string s1, string s2) {
int m = s1.size(), n = s2.size();
dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
// base case
for (int i = 1; i <= m; ++i) dp[i][0] = dp[i - 1][0] + s1[i - 1];
for (int j = 1; j <= n; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1];
// 状态转移方程
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 删除 s1[i] or s2[j]
// 比如 s1[0...i-1] == s2[0...j], 那么删除 s1[i] 两者就相等了
// dp[i][j] -> dp[i-1][j] 会增加删除和
dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
}
}
}
return dp[m][n];
}
};
🍻 子序列
🥂 5. 最长回文子串 [数组] [回文子串] (动态规划)
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 字符串 s[i...j] 的最长回文子串长度
int m_len = 1, start = 0, end = 0; // 记录最长回文子串的长度, start, end
public:
string longestPalindrome(string s) {
int n = s.size();
dp = vector<vector<int>>(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
}
for (int i = 0; i < n - 1; ++i) {
if (s[i] == s[i + 1]) {
dp[i][i + 1] = 2;
}
if (dp[i][i + 1] > m_len) {
m_len = dp[i][i + 1];
start = i;
end = i + 1;
}
}
// 状态转移
for (int len = 3; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
// 子串也是回文
if (s[i] == s[j] && dp[i + 1][j - 1] > 0) {
dp[i][j] = dp[i +1][j - 1] + 2;
// 更新最大子串信息
if (dp[i][j] > m_len) {
m_len = dp[i][j];
start = i;
end = j;
}
}
}
}
return s.substr(start, end - start + 1);
}
};
🥂 53. 最大子数组和 [数组] [子序列] (动态规划)
// 定义: 以 nums[i] 结尾的数的最大子数组和
class Solution {
private:
vector<int> dp; // 以 nums[i] 结尾的数的最大子数组和
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
dp = vector<int>(n, 0); // dp 初始化
// BASE CASE
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; ++i) {
dp[i] = max(nums[i], nums[i] + dp[i - 1]);
}
int res = *max_element(dp.begin(), dp.end());
return res;
}
};
🥂 139. 单词拆分 [字符串] > [单词拆分] > (动态规划)
// [字符串] > [单词拆分] > (动态规划)
// dp[i]: s[0...i) 是否可以被拼出
// dp[i] = dp[j] && uset.count(s[j...i)) -> s[0...i) = s[0...j) + s[j...i)
class Solution {
private:
vector<bool> dp;
unordered_set<string> uset; // 存放可以用于拼接的字符串
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
dp = vector<bool>(n + 1, false);
for (auto& word : wordDict) {
uset.insert(word);
}
// base case
dp[0] = true;
// 状态转移
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
// 如果 s[0...j) 可以被拼出, 且 s[j...i) 存在该单词
if (dp[j] && uset.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};
🥂 🌸 300. 最长递增子序列 [数组] [子序列] (动态规划)
// 定义: 以 nums[i] 结尾的最长子序列
class Solution {
private:
vector<int> dp; // 以 nums[i] 结尾的最长子序列
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
// base case
dp = vector<int>(n, 1); // 初始化备忘录
// 状态转移方程
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
// 从备忘录中获取最大子序列
int res = *max_element(dp.begin(), dp.end());
return res;
}
};
🥂 🌸 516. 最长回文子序列 [字符串] [子序列] [回文] (动态规划)
// 定义 dp[i][j]: 字符串 s[i...j] 的最长回文子序列
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: s[i...j] 的最长回文子序列
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
dp = vector<vector<int>>(n, vector<int>(n, 0));
// BASE CASE
for (int i = 0; i < n; ++i) dp[i][i] = 1;
// 状态转移方程
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
// 分别对应 去掉 i 处元素 or 去点 j 处元素 的回文数
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
};
🥂 🌸 1143. 最长公共子序列 [字符串] [子序列] (动态规划)
// 定义 dp[i][j]: 代表 s1[0...i] 与 s2[0...j] 的最长公共子序列
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 代表 s1[0...i] 与 s2[0...j] 的最长公共子序列
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
// base case
// dp[0][...] = 0, dp[...][0] = 0;
// 状态转移方程
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
};
🍻 路径和
🥂 🌸 64. 最小路径和 [矩阵] [路径和] (动态规划)
// 定义 dp[i][j]: 到达 (i,j) 的最小路径和
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 到达 (i,j) 的最小路径和
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
dp = vector<vector<int>>(m, vector<int>(n, 0));
// BASE CASE
dp[0][0] = grid[0][0];
for (int i = 1; i < m; ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < n; ++j) dp[0][j] = dp[0][j - 1] + grid[0][j];
// 状态转移方程
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
};
🍻 爬楼梯
🥂 70. 爬楼梯 [矩阵] [跳法] (动态规划)
class Solution {
private:
vector<int> dp; // dp[i]: 爬上第 i 层有多少种爬法
public:
int climbStairs(int n) {
dp = vector<int>(n + 1, 0);
// base case
dp[0] = 1, dp[1] = 1;
// 状态转移
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
🥂 🌸 174. 地下城游戏 [矩阵] [路径和] (动态规划) (逆向)
// 定义 dp[i][j]: 从 (i,j) 到达终点 (m-1, n-1) 的最小生命值
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 从 (i,j) 到达终点 (m-1, n-1) 的最小生命值
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
dp = vector<vector<int>>(m, vector<int>(n, 0));
// base case
dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
// 最后一列
for (int i = m - 2; i >= 0; --i) {
dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
}
// 最后一行
for (int i = n - 2; i >= 0; --i) {
dp[m - 1][i] = max(1, dp[m - 1][i + 1] - dungeon[m - 1][i]);
}
// 状态转移方程
for (int i = m - 2; i >= 0; --i) {
for (int j = n - 2; j >= 0; --j) {
// 选一个值较小的方向走
dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
}
}
return dp[0][0];
}
};
🥂 🌸 787. K 站中转内最便宜的航班 [图] [K步最短路径] (动态规划) (bellman ford)
// 定义 dp[i][j]: 走过 i 步后, 到达 j 的最小费用
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 走过 i 步后, 到达 j 的最短费用
const int INF = 0x3f3f3f3f;
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
// k 站 代表 k+1 条边
dp = vector<vector<int>>(k + 2, vector<int>(n, INF));
dp[0][src] = 0; // 走 0 步到达出发点的费用为 0
// 只走一步, 只走两步 ...
for (int i = 1; i <= k + 1; ++i) {
for (auto& flight : flights) {
// start, end 为一条边的两端
int start = flight[0], end = flight[1], cost = flight[2];
dp[i][end] = min(dp[i][end], dp[i - 1][start] + cost);
}
}
int res = INF;
// 经过一/2/3/...步到达终点的最小值
for (int i = 1; i <= k + 1; ++i) {
res = min(res, dp[i][dst]);
}
// 如果走 i 步根本到不了终点
return res == INF ? -1 : res;
}
};
🥂 🌸 931. 下降路径最小和 [矩阵] [路径和] (动态规划) (扩展边界)
// 定义 dp[i][j]: 到达 (i,j) 的最小路径和
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 到达 (i,j) 的最小路径和
vector<vector<int>> dirts = {{-1, -1}, {-1, 0}, {-1, 1}}; // 方向
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
dp = vector<vector<int>>(m, vector<int>(n + 2, INT_MAX));
// base case
for (int j = 1; j <= n; ++j) dp[0][j] = matrix[0][j - 1];
// 状态转移方程
for (int i = 1; i < m; ++i) {
for (int j = 1; j <= n; ++j) {
for (auto& dirt : dirts) {
// 左下, 正下, 右下
dp[i][j] = min(dp[i][j], dp[i + dirt[0]][j + dirt[1]]);
}
dp[i][j] += matrix[i][j - 1];
}
}
int res = *min_element(dp[m - 1].begin(), dp[m - 1].end());
return res;
}
};
🍻 其他
🥂 140. 单词拆分Ⅱ [字符串] (动态规划) (递归)
class Solution {
private:
unordered_set<string> uset; // 存放待对比的字符串
vector<vector<string>> dp; // 备忘录, 记录 s[i...] 可以拼的句子有哪几种
int n; // 字符串长度
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
int n = s.size(); this->n = n; // 字符串的长度
dp = vector<vector<string>>(n, vector<string>(0)); // dp 初始化
for (auto& word : wordDict) { // uset 初始化
uset.insert(word);
}
vector<int> res = traverse(s, 0); // 调用递归函数
return res;
}
// 获取 s[i...] 可以拼接的句子有哪些
vector<string> traverse(string s, int i) {
vector<string> cur_res; // 创建一个空的数组, 记录可行的字符串
// BASE CASE
if (i == n) { // 此时 s 字符串结束
cur_res.push_back("");
return cur_res;
}
// 获取备忘录, s[i...] 可以拼接的句子
if (!dp[i].empty()) {
return dp[i];
}
// 状态转移方程
for (int len = 1; len + i <= n; ++len) {
string subStr = s.substr(i, len); // 获取一个子单词
if (uset.count(subStr)) { // 这个子单词可以被拼接
vector<string> subFind = traverse(s, i + len); // 子任务可以拼接的字符串有哪些
for (auto& sub : subFind) {
if (sub.empty()) { // 防止最后一个单词后多个空格
cur_res.push_back(subStr);
} else {
cur_res.push_back(subStr + " " + sub);
}
}
}
}
// 更新备忘录
dp[i] = cur_res;
return cur_res;
}
};
🥂 514. 自由之路 [字符串] [操作次数] (动态规划)
// 定义 dp[i][j]: 当前匹配 key[0...i], 从 ring[j] 开始移动需要操作多少次
class Solution {
private:
vector<vector<int>> dp; // dp[i][j]: 当前匹配 key[0...i], 从 ring[j] 开始移动需要操作多少次
unordered_map<char, vector<int>> umap; // 字符对应的索引
public:
int findRotateSteps(string ring, string key) {
int m = key.size(), n = ring.size();
dp = vector<vector<int>>(m, vector<int>(n, INT_MAX));
for (int i = 0; i < n; ++i) {
umap[ring[i]].push_back(i);
}
// base case key[0][0] 需要的操作部数
for (auto& pos : umap[key[0]]) {
dp[0][pos] = min(dp[0][pos], cal(n, 0, pos) + 1);
}
// 状态转移
for (int i = 1; i < m; ++i) { // 先选取 key 中的一个字符
for (auto& pos : umap[key[i]]) {
// 从前一阶段的位置移动到当前位置的次数 dp[i][pos]
for (auto& prepos : umap[key[i - 1]]) {
dp[i][pos] = min(dp[i][pos], dp[i - 1][prepos] + cal(n, prepos, pos) + 1);
}
}
}
// RETURN 匹配 key[m] 但最终位置落于那个地方不确定
int res = *min_element(dp[m - 1].begin(), dp[m - 1].end());
return res;
}
// 从 a 到 b 需要的次数 [0, 1, 2, 3, 4, 5]
// n = 6, 从 2 移动到 4, (6 + 2 - 4) % 6 = 4 (6 + 4 - 2) % 6 = 2
int cal(int len, int a, int b) {
return min((len + a - b) % len, (len + b - a) % len);
}
};
🍺 贪心算法
🍻 区间重叠
🥂 🌸 252. 会议室 [区间数组] [重叠] (贪心)
// 其实就是判断是否存在重叠
class Solution {
private:
int cur_end = INT_MIN; // 当前和前一个的开始值
public:
bool canAttendMeetings(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
return a[1] < b[1];
});
// 开始遍历
for (auto& interval : intervals) {
int start = interval[0], end = interval[1];
// 有重叠
if (start < cur_end) return false;
// 无重叠
cur_end = end;
}
return true;
}
};
🥂 🌸 253. 会议室Ⅱ [区间数组] [重叠] (贪心)
// 求同一个时间点, 最多有几个区间重叠
class Solution {
private:
vector<int> start; // 开始的节点
vector<int> end; // 结束的节点
int res= 0, count = 0; // 最大的重叠数, 当前重叠数
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
int n = intervals.size();
for (auto& interval : intervals) {
start.push_back(interval[0]);
end.push_back(interval[1]);
}
// 添加并排序
sort(start.begin(), start.end());
sort(end.begin(), end.end());
// 开始遍历, start 起点肯定先遍历完
int i = 0, j = 0;
while (i < n) {
if (start[i] < end[j]) { // 找到开始点
count++;
i++;
} else { // 找到结束点, 或重合点, 重叠数都会减
count--;
j++;
}
res = max(res, count);
}
return res;
}
};
🥂 435. 无重叠区间 [区间数组] [重叠] (贪心)
class Solution {
private:
int count = 0; // 记录区间的数量
int cur_end = INT_MIN; // 记录当前区间结束的时间
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
return a[1] < b[1];
});
// 开始一个个遍历
for (auto& interval : intervals) {
int start = interval[0], end = interval[1];
// 需要移除区间
if (start < cur_end) {
count++;
continue;
}
cur_end = end;
}
return count;
}
};
🥂 452. 用最少数量的箭引爆气球 [区间数组] > [非重合区间] > (贪心)
// [区间数组] > [非重合区间] > (贪心)
class Solution {
private:
int res = 0; // 需要射的最少的箭数
long cur_end = LONG_MIN; // 上一个区间的 end [-wq, INT_MIN]
public:
int findMinArrowShots(vector<vector<int>>& points) {
// 按 end 排序
sort (points.begin(), points.end(), [](vector<int>& a, vector<int>& b) {
return a[1] < b[1];
});
// 开始遍历一个个区间
for (auto& point : points) {
int start = point[0], end = point[1];
// 碰到重叠区域, 这题擦边也可以射气球
if (start <= cur_end) continue;
// 没碰到重叠区域
res++;
cur_end = end;
}
return res;
}
};
🥂 1024. 视频拼接 [区间数组] [重叠] (贪心)
// 从 0 开始拼接, 之后在与当前区间重叠的区间中选 end 最大的区间
class Solution {
private:
int res = 0; // 需要的视频数
public:
int videoStitching(vector<vector<int>>& clips, int time) {
int n = clips.size();
sort(clips.begin(), clips.end(), [](vector<int>& a, vector<int>& b) {
if (a[0] == b[0]) return a[1] > b[1];
return a[0] < b[0];
});
if (clips[0][0] != 0) return -1;
if (n == 1 && clips[0][1] != time) return -1;
// 开始遍历
int cur_end = 0, next_end = 0; // 当前 end, 下一个临时 end
int i = 0; // 第 i 个视频
while (i < n && clips[i][0] <= cur_end) {
// 找下一个有重复区间的视频
while (i < n && clips[i][0] <= cur_end) {
// 选这两个符合条件的其中的最大 end 值
next_end = max(next_end, clips[i][1]);
i++;
}
// 此时已经找到合适的视频了
res++;
cur_end = next_end;
if (cur_end >= time) return res;
}
// 找不到
return -1;
}
};
🍻 跳跃
🥂 🌸 45. 跳跃游戏II [数组] [跳跃] (贪心)
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int end = 0; // 当前可以跳的位置 [1, 2, 3]
int jump = 0; // 跳的次数
int far = 0; // 可以跳的最远的距离
// 开始跳
for (int i = 0; i < n - 1; ++i) {
far = max(far, i + nums[i]); // 可以跳的最远距离
if (i == end) { // 到达最远距离后, 获取下一次最远距离
jump++;
end = far;
}
}
return jump;
}
};
🥂 🌸 55. 跳跃游戏 [数组] [跳跃] (贪心)
// 每一步都往最远了跳
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int far = 0; // 最远跳的距离
for (int i = 0; i < n - 1; ++i) {
far = max(far, i + nums[i]);
if (far <= i) return false;
}
// 判断能跳过去不
if (far < n - 1) return false;
return true;
}
};
🍻 子序列和
🥂 1090. 受标签影响的最大值 [映射数组] > [子序列和] > (贪心)
// [映射数组] > [子序列和] > (贪心)
class Solution {
private:
vector<pair<int, int>> pairs; // 记录初始值对应的下标索引
unordered_map<int, int> umap; // 记录标签情况
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
int n = values.size();
int res = 0, num = 0; // 总结果, 数字个数
pairs = vector<pair<int, int>>(n);
for (int i = 0; i < n; ++i) {
pairs[i] = make_pair(values[i], labels[i]);
}
// 按照 values 排序
sort(pairs.begin(), pairs.end(), [](pair<int, int>& a, pair<int, int>& b) {
return a.first > b.first;
});
// 贪心, 一个个拿
for (int i = 0; i < n && num < numWanted; ++i) {
int cur_v = pairs[i].first, cur_l = pairs[i].second;
if (umap[cur_l] < useLimit) {
umap[cur_l]++;
num++;
res += cur_v;
}
}
return res;
}
};
文章来源地址https://www.toymoban.com/news/detail-797052.html
文章来源:https://www.toymoban.com/news/detail-797052.html
到了这里,关于算法 - 动态规划 / 贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!