不同路径 II
问题描述
一个机器人位于一个 $m \times n$ 网格的左上角，他每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
问题分析
我们记 $dp[i, j]$ 为从 $(0, 0)$ 到 $(i, j)$ 的路径总数，$ob[i, j]$ 表示 $(i, j)$ 处有无障碍物（有障碍物则值为 $1$）。根据题目的规则，只能向下和向右走。因此从 $(0, 0)$ 到 $(i, j)$ 的路径总数等于从 $(0, 0)$ 到 $(i - 1, j)$ 和 $(i, j - 1)$ 两点坐标路径总数之和，即原问题可以由子问题递推得到。要注意这里要考虑到障碍物的问题，如果 $(i, j)$ 处是障碍物，则没有任何路径。于是可以得到下面的状态转移方程：
$$ \begin{align*} dp[i, j] = \left\{\begin{matrix} 0 & ob[i, j] = 1 \\ dp[i - 1, j] + dp[i, j - 1] & ob[i, j] = 0 \end{matrix}\right. \end{align*} $$算法代码
int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
{
const int m = obstacleGrid.size();
const int n = obstacleGrid[0].size();
// dp[i][j] 表示从坐标 (0, 0) 到 (i, j) 的路径数
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1; // 初始化
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (obstacleGrid[i][j] == 1)
{
// 遇到障碍物直接置零
dp[i][j] = 0;
}
else
{
// 否则统计右边和下面一共有多少条路径
if (i - 1 >= 0)
{
dp[i][j] += dp[i - 1][j];
}
if (j - 1 >= 0)
{
dp[i][j] += dp[i][j - 1];
}
}
}
}
return dp[m - 1][n - 1];
}
算法分析
- 时间复杂度：$O(mn)$
- 空间复杂度：$O(mn)$
打家劫舍 II
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。
问题分析
本题和打家劫舍的区别是房屋是环形的，也就是说不能够同时偷第一家和最后一家。因此需要对原问题稍作分解，分解为偷第 $1$ 到第 $n - 1$ 家和偷第 $2$ 到第 $n$ 家，取这两个子问题的最大值即可。
对于每个子问题，我们记 $w[i]$ 表示第 $i$ 家存放的金额，$dp[i]$ 表示偷第 $1$ 家到第 $i$ 家的最大总金额。很显然 $dp[i]$ 的值即为第一家的金额。依题意，多考虑偷一家，会存在如下两种情况：
- 如果当前这家没偷，那么可以偷下一家，上一家及其之前偷的金额可以汇总。
- 如果偷了当前这家，那么不可以偷下一家，当前偷得的金额还是和上一次偷完一样。
这两种情况取最大即可得到最优方案，如此递推算下去即可求解得到最终结果。因此，状态转移方程为：
$$ \begin{align*} dp[i] = \max \{dp[i - 2] + w[i], dp[i - 1]\} \end{align*} $$算法代码
int rob(vector<int> &nums)
{
const int n = nums.size();
vector<int> dp1(n, 0); // 偷第一家而不偷最后一家
vector<int> dp2(n, 0); // 偷最后一家而不偷第一家
if (n == 1)
{
// 只有一家
return nums[0];
}
// 初始化
dp1[0] = nums[0];
if (n > 1)
{
dp1[1] = max(nums[0], nums[1]);
dp2[1] = nums[1];
}
if (n > 2)
{
dp2[2] = max(nums[1], nums[2]);
}
for (int i = 2; i < n - 1; ++i)
{
dp1[i] = max(dp1[i - 2] + nums[i], dp1[i - 1]);
}
for (int i = 3; i < n; ++i)
{
dp2[i] = max(dp2[i - 2] + nums[i], dp2[i - 1]);
}
return max(dp1[n - 2], dp2[n - 1]);
}
算法分析
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
不同的子序列
问题描述
给定一个字符串 $s$ 和一个字符串 $t$，计算在 $s$ 的子序列中 $t$ 出现的个数。
字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
问题分析
本题和最长公共子序列类似。我们记 $dp[i, j]$ 表示 $s$ 的子串 $s[:i]$ 的子序列中 $t$ 的子串 $t[:j]$ 出现的个数。下面是两种简单情况：
- 如果 $j = 0$，即 $t[:j]$ 是空串，是任意字符串的子序列。应当设置 $dp[i, j] = 1$。
- 如果 $i < j$，说明 $t[:j]$ 比 $s[:i]$ 还长，$t[:j]$ 不可能是 $s[:i]$ 的子序列。
原问题与子问题存在如下两种关系：
- 如果之前对应位不能匹配，即 $s[i - 1] \ne t[j - 1]$，那么问题和 $dp[i - 1, j]$ 相当。因为 $t[:j]$ 删除掉倒数第二个字符 $t[j - 1]$ 后，可能会出现在 $s[:i - 1]$ 的子序列中。
- 如果之前的对应位能够匹配，即 $s[i - 1] = t[j - 1]$，那么原问题分解为如下两种情况之和：
- 认为 $s[i - 1]$ 和 $t[j - 1]$ 匹配，这个时候需要考察 $dp[i - 1, j - 1]$ 和 $dp[i - 1, j]$。
- 认为 $s[i - 1]$ 和 $t[j - 1]$ 不匹配，这个时候只需要考察 $dp[i - 1, j]$。
那么本题的状态转移方程为：
$$ \begin{align*} dp[i, j] = \left\{\begin{matrix} dp[i - 1, j] & s[i - 1] \ne t[j - 1] \\ dp(i - 1, j - 1) + dp[i - 1, j] & s[i - 1] = t[j - 1] \end{matrix}\right. \end{align*} $$算法代码
int numDistinct(string s, string t)
{
const int m = s.size(), n = t.size();
// dp[i][j] 表示 s 的子串 s[:i] 的子序列中 t 的子串 t[:j] 出现的个数
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0)); // 运算过程中可能溢出
for (int i = 0; i <= m; ++i)
{
for (int j = 0; j <= n; ++j)
{
if (j == 0)
{
// t[:j] 为空串，是任意字符串的子序列
dp[i][j] = 1;
}
else if (i < j)
{
// t[:j] 比 s[:i] 还长，不可能是 s[:i] 的子序列
dp[i][j] = 0;
}
else if (i > 0 && j > 0)
{
// 只有当 t[:j] 不比 s[:i] 长才有可能在 s[:i] 的子序列中出现
if (s[i - 1] != t[j - 1])
{
// 如果之前对应位不能匹配，那问题和 s[:i - 1] 的子序列是否有 t[:j] 相当
// 因为 t[:j] 删除掉倒数第二个字符 t[j - 1] 后，可能会出现在 s[:i - 1] 的子序列中
dp[i][j] = dp[i - 1][j];
}
else
{
// dp[i - 1][j - 1] 表示匹配 s[i] 和 t[j]
// dp[i - 1][j] 表示不匹配 s[i] 和 t[j]
// 最终子序列的出现的次数应为二者之和
dp[i][j] = dp[i - 1][j - 1] % 0x7fffffff + dp[i - 1][j] % 0x7fffffff;
// 虽然题目保证最终结果不会溢出，但中间结果还是会溢出，忽略高 32 位
}
}
}
}
return dp[m][n];
}
算法分析
- 时间复杂度：$O(mn)$
- 空间复杂度：$O(mn)$