本次作业力扣一维动态规划题目全部完成，多维动态规划还差 $3$ 题。
力扣 面试经典 150 题 - 一维动态规划
LeetCode 70. 爬楼梯
思路
第 $i$ 阶楼梯可以从 $i - 1$ 阶楼梯爬一阶爬到，也可以从 $i - 2$ 阶楼梯爬两阶爬到。故递推公式为：
$$
dp[i] = \begin{cases}1,&i=1,\2,&i=2,\dp[i - 1] + dp[i - 2],& otherwise.\end{cases}
$$
不难看出每个 $i$ 只会被计算一次，因此算法复杂度为 $\mathrm O(n)$。
代码
提交记录：0 ms (100.00%) / 5.98 MB (38.46%)
const int maxn = 55;
class Solution {
public:
int ans[55] = {0, 1, 2};
int climbStairs(int n) {
if (ans[n]) return ans[n];
return ans[n] = climbStairs(n - 1) + climbStairs(n - 2);
}
};
LeetCode 198. 打家劫舍
思路
令 $dp[i][j](i\in[1, n], j\in {0, 1})$ 表示已经偷了前 $i$ 个房间，且第 $i$ 个房间偷/不偷（$j=0/1$）能达到的最高金额。因此动态规划公式为：
$$
\begin{cases}
dp[i][0] = \max(dp[i - 1][0], dp[i - 1][1]),\
dp[i][1] = dp[i - 1][0] + nums[i].
\end{cases}
$$
我们不难发现更新过程中只会用到上一个状态，因此可以将第一维省略，采用滚动数组的形式来节省空间。
代码
提交记录：0 ms (100.00%) / 7.80 MB (18.09%)
class Solution {
public:
int rob(vector<int>& nums) {
int dp[2] = {0, 0};
for (int i = 0, x; i < nums.size(); ++i) x = max(dp[0], dp[1]), dp[1] = dp[0] + nums[i], dp[0] = x;
return max(dp[0], dp[1]);
}
};
LeetCode 139. 单词拆分
思路
本题可以直接使用动态规划来解决。令 $dp[i]$ 表示 $s$ 的前 $i$ 个字符能否被拆分为字典中的单词。因此动态转移方程为：$dp[i] = \max({dp[j]})(j\in [0, i - 1] 且 s[j + 1, i] \in wordDict)$。对于每个 $i$ 都需要以 $\mathrm O(n)$ 复杂度枚举 $j$，而对于每个 $j$ 同样需要 $\mathrm O(m)$ 的复杂度来检查（$m$ 为字典中单词长度）。因此算法复杂度为 $\mathrm O(n^2\cdot m)$，足够通过此题。
但拆分单词的过程就是去匹配字典的过程，如果是单个模式串的匹配，我们可以使用KMP算法，但是本题中需要匹配的是多个模式串，因此我们可以将KMP算法搬到字典树上，即AC 自动机。这样我们便可以用失配指针来加速 $dp[i]$ 的求解。但因为需要跳过每个节点的 fail 指针，因此这个过程并没有达到线性。这是令我们不太满意的，此时我们又观察到字典中单词的长度只有 $20$，因此可以考虑状态压缩优化DP，即将前 $20$ 位字母中，可能的子串长度存下来将其压缩成状态存在每个子节点的一个整数属性中。这样因为我们不再需要跳 fail 指针，因此整体复杂度便成功降到了 $\mathrm O(n)$。
代码
提交记录：4ms (93.46%) / 8.95MB (75.75%)
const int maxn = 305;
class Solution {
public:
int cnt, vis[maxn], ans, dp[maxn];
struct trie_node {
int son[26];
int fail, flag, depth;
unsigned stat;
void init() {
memset(son, 0, sizeof(son));
fail = flag = depth = 0;
}
} trie[10005];
queue<int> q;
void init(int len) {
for (int i = 0; i <= cnt; i++) trie[i].init();
for (int i = 1; i <= len; i++) vis[i] = 0;
cnt = 1;
ans = 0;
}
void insert(const string& s, int num) {
int u = 1;
for (int i = 0; i < s.length(); i++) {
int v = s[i] - 'a';
if (!trie[u].son[v]) trie[u].son[v] = ++cnt;
u = trie[u].son[v];
}
trie[u].flag = num;
return;
}
void getfail() {
for (int i = 0; i < 26; i++) trie[0].son[i] = 1;
q.push(1);
trie[1].fail = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
int Fail = trie[u].fail;
trie[u].stat = trie[Fail].stat;
if (trie[u].flag) trie[u].stat |= 1 << trie[u].depth;
for (int i = 0; i < 26; i++) {
int v = trie[u].son[i];
if (!v)
trie[u].son[i] = trie[Fail].son[i];
else {
trie[v].depth = trie[u].depth + 1;
trie[v].fail = trie[Fail].son[i];
q.push(v);
}
}
}
}
int query(const string& s) {
int u = 1, len = s.length(), mx = 0;
unsigned st = 1;
for (int i = 0; i < len; i++) {
int v = s[i] - 'a';
u = trie[u].son[v];
st <<= 1;
if (trie[u].stat & st) st |= 1, mx = i + 1;
}
return mx;
}
bool wordBreak(string s, vector<string>& wordDict) {
init(s.length());
for(int i = 0; i < wordDict.size(); ++i) insert(wordDict[i], i + 1);
getfail();
return query(s) == s.length();
}
};
LeetCode 322. 零钱兑换
思路
假设 $dp[i]$ 表示凑成 $i$ 元最少需要的硬币个数，因此动态转移方程为：$dp[i] = \min_{j\in coins}({dp[i - j] + 1})$。不难发现每个 $i$ 只会被计算一次，因此算法复杂度为 $\mathrm O(n)$。
代码
提交记录：40ms (97.56%) / 9.95MB (95.14%)
const int maxn = 1e4 + 7;
class Solution {
public:
int dp[maxn];
int coinChange(vector<int>& coins, int amount) {
for (int i = 1; i <= amount; ++i)
for (auto coin : coins)
if (coin < i && dp[i - coin] > 0) dp[i] = dp[i] ? min(dp[i], dp[i - coin] + 1) : dp[i - coin] + 1;
else if (coin == i) dp[i] = 1;
return dp[amount] || !amount ? dp[amount] : -1;
}
};
LeetCode 300. 最长递增子序列
思路
假设 $dp[i]$ 表示以 $i$ 结尾的最长递增子序列的长度，因此动态转移方程为：$dp[i] = \max({dp[k] + 1})(k\in [1, i - 1] 且 dp[k] < dpk[i])$，算法复杂度为 $\mathrm O(n^2)$。
观察到题目中提示存在复杂度为 $\mathrm O(n\log n)$ 的算法，因此我们可以考虑使用二分查找来优化。我们令 $g[i]$ 表示长度为 $i$ 的最长递增子序列的最小结尾元素，因此 $g$ 序列是单调递增的，这样我们便可以使用二分查找来找到 $g$ 序列中第一个大于等于 $nums[i]$ 的元素，然后将其替换为 $nums[i]$。不难发现，$g$ 序列的长度便是最长递增子序列的长度，因此我们只要在遍历时不断更新 $g$ 序列的最长长度即可。因为只需要遍历一次，而每次在 $g$ 中二分查找的复杂度为 $\mathrm O(\log n)$，因此总的算法复杂度为 $\mathrm O(n\log n)$。
代码
提交记录：8ms (93.87%) / 10.17MB (36.89%)
class Solution {
public:
int g[20000], ans;
int lengthOfLIS(vector<int>& nums) {
memset(g, 0x3f, sizeof(g));
g[0] = -0x3f3f3f3f;
for (int i = 1; i <= nums.size(); ++i) {
int x = lower_bound(g, g + 20000, nums[i - 1] + 10000) - g;
ans = max(ans, x);
g[x] = min(g[x], nums[i - 1] + 10000);
}
return ans;
}
};
力扣 面试经典 150 题 - 多维动态规划
LeetCode 120. 三角形最小路径和
思路
观察可发现，每个位置 $(i, j)$ 的最小路径和只与上一行相邻的两个位置 $(i - 1, j - 1)$ 和 $(i - 1, j)$ 有关，因此可以写出动态转移方程为：$dp[i][j] = \min({dp[i - 1][j - 1], dp[i - 1][j]}) + triangle[i][j]$。因为三角形中每个位置只会被计算一次，因此算法复杂度为 $\mathrm O(n^2)$。注意边界条件的处理即可。
代码
提交记录：4ms (93.64%) / 8.42MB (69.82%)
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int ans = 201000000;
for (int i = 1; i < triangle.size(); ++i){
triangle[i][0] += triangle[i - 1][0], triangle[i][i] += triangle[i - 1][i - 1];
for (int j = 1; j < i; ++j) triangle[i][j] += min(triangle[i - 1][j], triangle[i - 1][j - 1]);
}
for (int i = 0; i < triangle.size(); ++i) ans = min(ans, triangle[triangle.size() - 1][i]);
return ans;
}
};
LeetCode 64. 最小路径和
思路
假设 $dp[i][j]$ 表示从 $(0, 0)$ 到 $(i, j)$ 的最小路径和，因此动态转移方程为：$dp[i][j] = \min({dp[i - 1][j], dp[i][j - 1]}) + grid[i][j]$。因为每个位置只会被计算一次，因此算法复杂度为 $\mathrm O(n^2)$。
代码
提交记录：4ms (98.38%) / 9.43MB (78.78%)
const int maxn = 200 * 200 * 200;
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[i].size(); ++j)
if (i || j) grid[i][j] += min(i ? grid[i - 1][j] : maxn, j ? grid[i][j - 1]: maxn);
return grid[grid.size() - 1][grid[0].size() - 1];
}
};
LeetCode 63. 不同路径 II
思路
令 $dp[i][j]$ 表示从 $(0, 0)$ 到 $(i, j)$ 的不同路径数，因此动态转移方程为：$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$。因为每个位置只会被计算一次，因此算法复杂度为 $\mathrm O(n^2)$。在实际计算中，我们可以直接将结果存到原数组中，以节省空间。为了区别开路径数量和障碍物，我们可以将障碍物的值设为 $1$，而初始位置路径数量的值设为 $-1$，这样我们就可以通过数字的正负来区分障碍物和路径数量。
代码
提交记录：0ms (100.00%) / 7.53MB (38.39%)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
for (int i = 0; i < obstacleGrid.size(); ++i)
for (int j = 0; j < obstacleGrid[i].size(); ++j)
{
if (obstacleGrid[i][j] == 1) continue;
if (!i && !j) obstacleGrid[i][j] = -1;
if (i && obstacleGrid[i - 1][j] != 1) obstacleGrid[i][j] += obstacleGrid[i - 1][j];
if (j && obstacleGrid[i][j - 1] != 1) obstacleGrid[i][j] += obstacleGrid[i][j - 1];
}
return obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1] > 0 ? 0 : -obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
}
};
LeetCode 97. 交错字符串
思路
令 $dp[i][j]$ 表示 $s_1$ 的前 $i$ 个字符和 $s_2$ 的前 $j$ 个字符能否交错组成 $s_3$ 的前 $i + j$ 个字符。因此动态转移方程为：$dp[i][j] = \begin{cases}dp[i - 1][j], &s_1[i - 1] = s_3[i + j - 1];\ dp[i][j - 1], &s_2[j - 1] = s_3[i + j - 1].\end{cases}$，即第 $i + j$ 个字符只能从 $s_1$ 的第 $i$ 个字符或 $s_2$ 的第 $j$ 个字符中选取。因为每个位置只会被计算一次，因此算法复杂度为 $\mathrm O(n^2)$。
可以发现，在 $i + j$ 相同的情况下，$i$ 确定后便可以确定 $j$，因此我们可以将第一维省略，采用滚动数组的形式来节省空间，只用 $dp[i]$ 来进行更新。
代码
提交记录：0ms (100.00%) / 6.22MB (83.71%)
const int maxn = 205;
class Solution {
public:
int dp[maxn];
bool isInterleave(string s1, string s2, string s3) {
dp[0] = s2[0] == s3[0], dp[1] = s1[0] == s3[0];
for (int i = 1; i < s3.length(); ++i)
for (int j = min((int)s1.length(), i + 1); j >= 0; --j)
dp[j] = (dp[j] && i >= j && s2[i - j] == s3[i]) || (j && dp[j - 1] && s1[j - 1] == s3[i]);//, printf("%d,%d: %d(%d %d)\n", i + 1, j, dp[j]);
return dp[s1.length()] && s1.length() + s2.length() == s3.length();
}
};
LeetCode 72. 编辑距离
思路
令 $dp[i][j]$ 表示将 $word1$ 的前 $i$ 个字符转换为 $word2$ 的前 $j$ 个字符所需要的最少操作数。因此动态转移方程为：$dp[i][j] = \begin{cases}dp[i - 1][j - 1], &word1[i - 1] = word2[j - 1];\ \min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1, &otherwise.\end{cases}$，即第 $i$ 个字符和第 $j$ 个字符相同则不需要操作，否则需要进行替换、插入或删除操作。因为每个位置只会被计算一次，因此算法复杂度为 $\mathrm O(n^2)$。
代码
提交记录：0ms (100.00%) / 7.16MB (89.49%)
class Solution {
public:
int minDistance(string word1, string word2) {
int dp[word1.length() + 1][word2.length() + 1];
for (int i = 0; i <= word1.length(); ++i)
for (int j = 0; j <= word2.length(); ++j)
{
dp[i][j] = 500;
if (!i && !j) dp[i][j] = 0;
if (i && j) dp[i][j] = min(dp[i - 1][j - 1] + (word1[i - 1] != word2[j - 1]), dp[i][j]); // same or exchange
if (j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1); // insert
if (i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1); // delete
}
return dp[word1.length()][word2.length()];
}
};
