LeetCode-Day27——动态规划专题
97. 交错字符串
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
1
2
| 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
|
示例 2:
1
2
| 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
|
思路：动态规划
划重点：
dp[i][j]表示s1的前i个字符和s2的前j个字符是否能够交错生成s3的前i+j个字符。
dp[0][0] = 1：因为当所有都为空的时候，就已经符合条件了
初始化的时候第一行为dp[0][i] = dp[0][i - 1] && s2[i - 1] == s3[i - 1]
同理，第一列为dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1]
（初始化非常非常重要，一定要从空开始考虑，而不要从第一个字符开始考虑，否则会遇到很多bug然后通不过）
然后动态规划的方程为
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])
这样就可以写出Code了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.length(), len2 = s2.length();
if(s3.length() != s1.length() + s2.length()) {
return false;
} else if(len1 == 0 && len2 == 0) {
return s3.length() == 0 ? true : false;
} else if(len1 == 0 || len2 == 0) {
return (s3 == s1 || s3 == s2) ? true : false;
}
bool dp[len1 + 1][len2 + 1] = {{0}};
dp[0][0] = 0;
for(int i = 1;i <= len1;i++) {
dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
}
for(int i = 1;i <= len2;i++) {
dp[0][i] = dp[0][i - 1] && s2[i - 1] == s3[i - 1];
}
for(int i = 1;i <= len1;i++) {
for(int j = 1;j <= len2;j++) {
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
}
}
return dp[len1][len2];
}
};
|
115. 不同的子序列
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入: S = "rabbbit", T = "rabbit"
输出: 3
解释:
如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^
|
示例 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 输入: S = "babgbag", T = "bag"
输出: 5
解释:
如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^
|
思路：
dp[i][j]表示t的前i个字符与s的前j个字符匹配的个数。
如果t的第i个字符和s的第j的字符一样的话，那么dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
如果不一样的话， dp[i][j] = dp[i][j - 1]。
Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int numDistinct(string s, string t) {
int len1 = s.length(), len2 = t.length();
long long dp[len2 + 1][len1 + 1] = {0};
for(int i = 0;i <= len1;i++) {
dp[0][i] = 1;
}
for(int i = 1;i <= len2;i++) {
for(int j = 1;j <= len1;j++) {
if(t[i - 1] == s[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[len2][len1];
}
};
|
注意：不过不用long long的话，只用int会爆掉。
132. 分割回文串II
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
1
2
3
| 输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
|
解释：这里一维动态规划，但是这里的想法很难想到（我很难…想到…
首先初始化整个数组的内容为自己的下标，即一个字母就是一个分割。然后遍历每一个点，以该点为回文中心，向两边更新（注意考虑奇数偶数两种情况）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int minCut(string s) {
int len = s.length();
int dp[len + 1];
for(int i = 0;i <= len;i++) {
dp[i] = i - 1;
}
for(int i = 0;i < len;i++) {
dp[i + 1] = min(dp[i + 1], dp[i] + 1);
if(i == len - 1) {
break;
}
int start = i, end = i + 1;
while(start >= 0 && end < len && s[start] == s[end]) {
dp[end + 1] = min(dp[end + 1], dp[start] + 1);
start--, end++;
}
start = i - 1, end = i + 1;
while(start >= 0 && end < len && s[start] == s[end]) {
dp[end + 1] = min(dp[end + 1], dp[start] + 1);
start--, end++;
}
}
return dp[len];
}
};
|
174. 地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
1
2
3
4
5
6
7
8
9
10
11
| 例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
|
思路：依然是动态规划。
但是不一样的是，这道题需要倒着考虑，你需要从右下角位置P处生命值至少为1开始倒着计算。
每一个点的生命值由它右边或下面的生命值求解，但需要注意的是，求解出来的生命值需要和1进行比较，比如，求解出来的生命值为负值（即后面有可能遇到加了很多生命值的情况），但是在该点[i][j]仍然需要满足生命值大于等于1的请款，因此会有max(1, min(nums[i + 1][j], nums[i][j + 1]) - dungeon[i][j])的表达式产生！
Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int row = dungeon.size(), col = dungeon[0].size();
int nums[row][col];
nums[row - 1][col - 1] = max(1,1 - dungeon[row - 1][col - 1]);
for(int i = row - 2;i >= 0;i--) {
nums[i][col - 1] = max(1, nums[i + 1][col - 1] - dungeon[i][col - 1]);
}
for(int i = col - 2;i >= 0;i--) {
nums[row - 1][i] = max(1, nums[row - 1][i + 1] - dungeon[row - 1][i]);
}
for(int i = row - 2; i >= 0; i--) {
for(int j = col - 2;j >= 0;j--) {
nums[i][j] = max(1, min(nums[i + 1][j], nums[i][j + 1]) - dungeon[i][j]);
}
}
return nums[0][0];
}
};
|
213. 打家劫舍II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
思路：这里需要注意的是环形，因此不能简单的考虑dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])，因为你需要注意第一个是否拿过，因此，我们就设置两种情况，一种是强制拿第一个，另一种就是强制不拿第一个。
所以我们使用二维的dp[n][2]数组。
dp[0][0]表示不拿第一个,dp[0][1]表示拿第一个，则推导初始情况：
dp[0][0] = 0, dp[1][0] = nums[1], dp[0][1] = nums[0], dp[1][1] = nums[0]
然后写动态转移方程的时候需要注意dp[i][0]只能从dp[j][0]转移过来，dp[i][1]只能从dp[j][1]转移过来。
最后返回最值的时候，只要dp[n - 1][0]和dp[n - 2][1]之间考虑即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if(len == 0) {
return 0;
} else if(len < 3) {
return nums.size() == 1 ? nums[0] : max(nums[0], nums[1]);
}
int dp[len][2];
dp[0][0] = 0, dp[1][0] = nums[1], dp[0][1] = nums[0], dp[1][1] = nums[0];
for(int i = 2;i < len;i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 2][0] + nums[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 2][1] + nums[i]);
}
return max(dp[len - 1][0], dp[len - 2][1]);
}
};
|