codetop标签动态规划大全C++讲解(二)！！动态规划刷穿地心！！学吐了家人们o(╥﹏╥)o
一篇只有十题左右，写少一点好复习
- 1.目标和
- 2.分割等和子集
- 3.完全平方数
- 4.比特位计数
- 5.石子游戏
- 6.预测赢家
- 7.不同的二叉搜索树
- 8.解码方法
- 9.鸡蛋掉落
- 10.正则表达式匹配
- 11.通配符匹配
- 12.交错字符串
1.目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
sum_pos - sum_neg = sum
sum_pos + sum_neg = target
所以：sum_pos = (target + sum) % 2
01背包问题
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((target + sum) % 2 != 0) return 0;
if(abs(target) > sum) return 0;
int sum_pos = (target + sum) / 2;
// 背包是sum_pos,nums中的值是物品,只能使用一次，是0-1背包
vector<int> dp(sum_pos + 1, 0);
dp[0] = 1;
for(int i = 0; i < nums.size(); i ++){
for(int j = sum_pos; j >= nums[i]; j --){
dp[j] += dp[j - nums[i]];
}
}
return dp[sum_pos];
}
};
2.分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
一个子集的大小就除2，这就是背包容量，nums里面的元素是物品，由于每个元素只能用一次，所以是01背包
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int i = 0; i < nums.size(); i ++){
sum += nums[i];
}
if(sum % 2 != 0) return false;
int target = sum / 2;
//初始化
vector<int> dp(target + 1, 0);
for(int i = 0; i < nums.size(); i ++){
for(int j = target; j >= nums[i]; j --){
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if(dp[target] == target) return true;
return false;
}
};
3.完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例：
- 输入：n = 12
- 输出：3
- 解释：12 = 4 + 4 + 4
平方数就是物品，并且可以无限次使用，n是背包容量，现在问凑满这个背包最少需要多少物品
dp[j] = min(dp[j]，dp[j - i * i] + 1)
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for(int i = 1; i * i<= n; i ++){//物品
for(int j = i * i; j <= n; j ++){//背包
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};
4.比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
有一个极其巧妙的做法：
偶数的二进制1个数超级简单，因为偶数相当于是被更小的某个数乘2，这个乘2在二进制中的体现就是整体左移，比如数字1的二进制是1，左移是10，就是2。所以1的个数是不变的，只是多了个0，dp[i] = dp[i / 2]
奇数就更简单了，奇数由不大于数的偶数+1，偶数+1在二进制上会发生什么？就是某位加1，所以dp[i] = dp[i / 2] + 1
class Solution {
public:
vector<int> countBits(int n) {
int i = 1;
vector<int> dp(n + 1, 0);
for(int i = 0; i <= n; i ++){
if(i % 2 == 0) dp[i] = dp[i / 2];
else dp[i] = dp[i - 1] + 1;
}
return dp;
}
};
5.石子游戏
Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。
Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。
假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。
用二维数组 dp[i][j] 记录 piles[i] ~ piles[j] 序列中，先选择的人可以获得比对手多的石子数量。
- 若选择piles[i]，则对手可选的范围变为piles[i + 1] ~ piles[j]，选择piles[i]后，先手变成后手，对手可选择的石子数量为dp[i + 1][j]，则我们比对手多的石子的数量记为dp[i][j] = piles[i] - dp[i + 1][j]。
- 若选择piles[j],则对手可选的范围变为 piles[i]~piles[j-1] ，选择piles[j]后，我们变为后手，所以对手可选择的比我们多的石子的数量为 dp[i][j-1]，则我们比对手多的石子的数量记为dp[i][j] = piles[j]- dp[i][j-1]。
所以 dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
遍历是从小范围到大范围，为了保证每次计算依赖的值已经被计算过，应该先遍历数组长度len，再遍历l和r
class Solution {
public:
bool stoneGame(vector<int>& piles) {
int n = piles.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = 0; i < n; i++) {
dp[i][i] = piles[i];
}
for (int len = 2; len <= n; len++) {
for (int l = 0; l <= n - len; l++) {
int r = l + len - 1;
dp[l][r] = max(piles[l] - dp[l + 1][r], piles[r] - dp[l][r - 1]);
}
}
return dp[0][n - 1] > 0;
}
};
6.预测赢家
给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
和石子游戏区别不大
class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = nums[i];
for (int len = 2; len <= n; len++) {
for (int l = 0; l <= n - len; l++) {
int r = l + len - 1; // r是右端点
dp[l][r] = max(nums[l] - dp[l + 1][r], nums[r] - dp[l][r - 1]);
}
}
return dp[0][n - 1] >= 0;
}
};
7.不同的二叉搜索树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
dp[i]表示i个节点的二叉搜索树共有多少种
确定递推公式，先观察dp[3]怎么得出来的
dp[3]，就是元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
- 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
- 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
- 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
所以dp[i] += dp[j - 1] * dp[i - j]
初始化，空树也是二叉搜索树，dp[0] = 1
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= i; j ++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};
8.解码方法
dp[i]表示以第i个字符为结尾，解码方法的总数
- s[i] 和 s[i - 1] 是单独为一个字符形成两个数字，那么dp[i]的值就是dp[i-1]的值；
- 如果 s[i] 和 s[i-1] 合并为一个字符形成为一个数字，那么 dp[i] 的值就是 dp[i-2] 的值。因为 s[i] 和 s[i-1] 都形成一个数字了，再 dp[i] 往前就是就是 dp[i-2] 了。
- 因为单独一个0不能解码，所以当s[i]和s[i-1]是单独为一个字符时，若s[i]==‘0’，dp[i] = 0
- 如果形成的2位数数字不在[10,26]区间内的话，所以当s[i]和s[i-1]合并为一个字符时，若超出这个范围了，dp[i] = 0
所以状态转移方程包含dp[i-1]和dp[i-2]
那么需要初始化dp[0]和dp[1]
dp[0]只需要判断他是不是0，即可得出结论
dp[1]的话有两种情况，合为一个数；分开成两个数。合为一个数需要判断形成的这一个数是否在[10, 26]这个范围里面；分别为两个数只需要判断s[0]和s[1]是不是都不为’0’。
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<int> dp(n, 0);
if(s[0] != '0') dp[0] = 1;
if(n == 1) return dp[0];
if(s[0] != '0' && s[1] != '0') dp[1] = 1;
int count = (s[0] - '0') * 10 + (s[1] - '0');
if(count >= 10 && count <= 26) dp[1] ++;
for(int i = 2; i < n; i ++){
if(s[i] != '0') dp[i] += dp[i - 1];
int count = (s[i - 1] - '0') * 10 + (s[i] - '0');
if(count >= 10 && count <= 26) dp[i] += dp[i-2];
}
return dp[n - 1];
}
};
9.鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
没有鸡蛋个数的限制的话，肯定是二分法效率最高
有鸡蛋限制的话，先留一个鸡蛋，其他二分法或者是多分法，找到鸡蛋碎的区间，在拿最后一个鸡蛋逐步试楼层
dp[k][n] 表示有 k 个鸡蛋和 n 层楼时，最少的扔鸡蛋次数。
状态转移方程：对于每个楼层 i，我们考虑两种情况：
鸡蛋碎了，问题转化为 k-1 个鸡蛋和 i-1 层楼的问题。
鸡蛋没碎，问题转化为 k 个鸡蛋和 n-i 层楼的问题。
取两者中的最大值，然后加 1，表示在第 i 层扔鸡蛋所需的最少次数。
class Solution {
public:
int superEggDrop(int K, int N) {
// dp[i][j] 表示 i 个鸡蛋，j 层楼时的最少尝试次数
vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
// 初始化 base case
// 如果只有一个鸡蛋，只能线性扫描，每层楼都要试，最坏情况的次数就是最少次数
for (int j = 1; j <= N; j++) {
dp[1][j] = j;
}
for (int i = 2; i <= K; i++) {
for (int j = 1; j <= N; j++) {
int left = 1, right = j;
int res = INT_MAX;
// 二分搜索，优化线性扫描
while (left <= right) {
int mid = (left + right) / 2;
int broken = dp[i - 1][mid - 1];
int notBroken = dp[i][j - mid];
// 在最坏情况下的最少尝试次数
if (broken > notBroken) {
right = mid - 1;
res = min(res, broken + 1);
} else {
left = mid + 1;
res = min(res, notBroken + 1);
}
}
dp[i][j] = res;
}
}
// 答案在 dp[K][N] 中
return dp[K][N];
}
};
10.正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘※’ 的正则表达式匹配。
- ‘.’匹配任意单个字符
- ‘※’匹配零个或多个前面的那一个元素
s 和 p 相互匹配的过程大致是，两个指针 i, j 分别在 s 和 p 上移动，如果最后两个指针都能移动到字符串的末尾，那么就匹配成功，反之则匹配失败。
其实.很好匹配，遇到.无脑匹配就可以了，但是 ※ 很厉害了，他可以让之前的那个字符重复任意次数，包括0次，意味着这个是空字符串也没事。“.a※b”可以匹配文本“zaaab”，也可以匹配“cb”。而模式串“ .※ ”更厉害了，他可以匹配任何文本，包括空字符串。
如果i到了s的末尾，j没有到p的末尾，这时候就要考虑p剩余的元素能否匹配空字符串。什么能匹配空字符串呢？
- ‘.’不行，因为 ‘.’ 自身并不意味着可以选择不匹配任何字符。它总是匹配一个字符，无论是字母、数字还是符号。因此，. 不能单独用来表示“匹配空字符串”的意思。
- ‘ * ’用于指定其前一个字符可以出现 0 次、1 次或多次。它的关键在于 * 可以让前面的字符出现次数为零，这就意味着完全可以不匹配任何字符。
现在开始一步一步写代码，如果不考虑※通配符，面对两个待匹配字符s[i]和p[j]，我们唯一能做的就是考虑她俩是否匹配。
bool isMatch(string s, string p){
int i = 0, j = 0;
while(i < s.size() && j < p.size()){
if(s[i] == p[j] || p[j] == '.'){
i ++; j ++;
}else{
return false;
}
}
return i == j;
}
如果加入 ※ 匹配符，局面就会复杂一些。
当p[j + 1] 为 ※ 通配符时，分情况讨论：
- 如果s[i] == p[j]，那么有两种情况：
- p[j] 有可能会匹配多个字符，比如 s = “aaa”, p = “a*”，那么 p[0] 会通过 * 匹配 3 个字符 “a”。
- p[i] 也有可能匹配 0 个字符，比如 s = “aa”, p = “a*aa”，由于后面的字符可以匹配 s，所以 p[0] 只能匹配 0 次。
- 如果 s[i] != p[j]，只有一种情况：
- p[j] 只能匹配 0 次，然后看下一个字符是否能和 s[i] 匹配。比如说 s = “aa”, p = “b*aa”，此时 p[0] 只能匹配 0 次。
if(s[i] == p[j] || p[j] == '.'){
//匹配
if(j < p.size() - 1 && p[j + 1] == '*'){
// 有 * 通配符，可以匹配 0 次或多次
} else {
// 无 * 通配符，老老实实匹配 1 次
i ++; j ++;
}
}else{
// 不匹配
if(j < p.size() - 1 && p[j + 1] == '*'){
// 有 * 通配符，只能匹配0
}else{
// 无 * 通配符，匹配无法进行下去了
return false;
}
}
定义dp函数bool dp(string s, int i, string p, int j)
若 dp(s, i, p, j) = true，则表示 s[i…] 可以匹配 p[j…]；若 dp(s, i, p, j) = false，则表示 s[i…] 无法匹配 p[j…]。
根据这个定义，我们想要的答案就是 i = 0, j = 0 时 dp 函数的结果：
bool dp(string s, int i, string p, int j) {
if (s[i] == p[j] || p[j] == '.') {
// 匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 1.1 通配符匹配 0 次或多次
// 先执行第一个再执行第二个
return dp(s, i, p, j + 2) || dp(s, i + 1, p, j);
} else {
// 1.2 常规匹配 1 次
return dp(s, i + 1, p, j + 1);
}
} else {
// 不匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 2.1 通配符匹配 0 次
return dp(s, i, p, j + 2);
} else {
// 2.2 无法继续匹配
return false;
}
}
}
解析：
- 通配符匹配0次或多次dp(s, i, p, j + 2)
将j加2，i不变，含义就是直接跳过p[j]和之后的通配符，即通配符匹配0次。
即使s[i] == p[j]，依然可能出现匹配0次这种情况，如下图：
- 匹配多次的情况dp(s, i + 1, p, j)
将i加1，j不变，含义就是p[j]匹配了s[i]，但p[j]还可以继续匹配，即通配符匹配多次的情况。
- 常规匹配1次。无 * 的常规匹配。如果 s[i] == p[j]，就是 i 和 j 分别加一。
- 不等。通配符匹配0次。将j加2，i不变。
- 不等且无*，匹配失败
完整代码：
考这个我就去死(╯>д<)╯⁽˙³˙⁾
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
// dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
// 空字符串和空模式是匹配的
dp[0][0] = true;
// 处理 p 开头是 '*' 的情况
for (int j = 1; j < n; j += 2) {
if (p[j] == '*') {
dp[0][j + 1] = dp[0][j - 1];
} else {
break;
}
}
// 填充 dp 表格
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
// '*' 可以匹配零个或多个字符
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
} else {
// 逐字符匹配，或者 '.' 可以匹配任意字符
dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
}
}
}
// 最终结果
return dp[m][n];
}
};
11.通配符匹配
给你一个输入字符串 (s) 和一个字符模式 ( p) ，请你实现一个支持 ’ ? ’ 和 ’ * ’ 匹配规则的通配符匹配：
- ’ ? ’ 可以匹配任何单个字符。
- ’ * ’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
唯一需要注意的是本题的测试用例可能出现很多 * 连续出现的情况，很容易看出连续多个 * 和一个 * 的通配效果是一样的，所以我们可以提前删除连续的 * 以便提升一些效率。
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
// dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
// 空字符串和空模式是匹配的
dp[0][0] = true;
// 处理 p 开头是 '*' 的情况
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// 填充 dp 表格
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
// 单个字符匹配，或 '?' 匹配任意一个字符
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == '*') {
// '*' 可以匹配零个或多个字符
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
// 最终结果
return dp[m][n];
}
};
12.交错字符串
给定三个字符串s1，s2，s3，请你帮忙验证s3是否是由s1与s2交错组成的。
实则就是一个使用双指针技巧合并两个字符串的过程。
但本题跟普通的数组/链表双指针技巧不同的是，这里需要穷举所有情况。比如 s1[i], s2[j] 都能匹配 s3[k] 的时候，到底应该让谁来匹配，才能完全合并出 s3 呢？回答这个问题很简单，我不知道让谁来，那就都来试一遍好了。
所以本题肯定需要一个递归函数来穷举双指针的匹配过程，然后用一个备忘录消除递归过程中的重叠子问题，也就能写出自顶向下的递归的动态规划解法了。
class Solution {
private:
vector<vector<int>> memo;
bool dp(string& s1, int i, string& s2, int j, string& s3){
// base case
int k = i + j;
if(k == s3.size()) return true;
if(memo[i][j] != -1) return memo[i][j] == 1;
bool res = false;
if(i < s1.size() && s1[i] == s3[k]) res = dp(s1, i + 1, s2, j, s3);
if(j < s2.size() && s2[j] == s3[k]) res = res || dp(s1, i, s2, j + 1, s3);
memo[i][j] = res ? 1 : 0;
return res;
}
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if(m + n != s3.size()) return false; // 长度不对的话，不可能对
memo = vector<vector<int>>(m + 1, vector<int>(n + 1, -1));
return dp(s1, 0, s2, 0, s3);
}
};