目录
前言
面试题 98 : 路径的数目
面试题 99 : 最小路径之和
面试题 100 : 三角形中最小路径之和
前言
矩阵路径是一类常见的可以用动态规划来解决的问题。这类问题通常输入的是一个二维的格子,一个机器人按照一定的规则从格子的某个位置走到另一个位置,要求计算路径的条数或找出最优路径。
矩阵路径相关问题的状态转移方程通常有两个参数,即 f(i, j) 的两个参数 i、j 通常是机器人当前到达的坐标。需要根据路径的特点找出到达坐标 (i, j) 之前的位置,通常是坐标 (i - 1, j - 1)、(i - 1, j)、(i, j - 1) 中的一个或多个。相应地,状态转移方程就是找出 f(i, j) 与 f(i - 1, j - 1)、f(i - 1, j) 或 f(i, j - 1) 的关系。
可以根据状态转移方程写出递归代码,但值得注意的是一定要将 f(i, j) 的结果用一个二维数组缓存,以避免不必要的重复计算。也可以将计算所有 f(i, j) 看成填充二维表格的过程,相应地,可以创建一个二维数组并逐一计算每个元素的值。通常,矩阵路径相关的问题的代码都可以优化空间效率,用一个一维数组就能保存所有必需的数据。
接下来列举几个高频的矩阵类型的问题。
面试题 98 : 路径的数目
题目:
一个机器人从 m x n 的格子的左上角出发,它每步要么向下要么向右,直到抵达格子的右下角。请计算机器人从左上角到达右下角的路径的数目。例如,如果格子的大小是 3 x 3,那么机器人从左上角到达右下角有 6 条符合条件的不同路径,如下图所示。
分析:
机器人每次只能走一步,它从格子的左上角到达右下角需要走多步。机器人每走一步都有两个选择,要么向下走要么向右走。一个任务需要多个步骤才能完成,每步面临若干选择,这类问题看起来可以用回溯法解决,但由于这个题目只要求计算从左上角到达右下角的路径的数目,并没有要求列出所有的路径,因此这个问题更适合用动态规划解决。
分析确定状态转移方程:
应用动态规划解决问题的关键在于找出状态转移方程。可以用函数 f(i, j) 表示从格子的左上角坐标为 (0, 0) 的位置出发到达坐标为 (i, j) 的位置的路径的数目。如果格子的大小为 m x n,那么 f(m - 1, n - 1) 就是问题的解。
-
当 i 等于 0 时,机器人位于格子最上面一行,机器人不可能从某个位置向下走一步到达一个行号 i 等于 0 的位置。因此,f(0, j) 等于 1,即机器人只有一种方法可以到达坐标为 (0, j) 的位置,即从 (0, j - 1) 的位置向右走一步。
-
当 j 等于 0 时,机器人位于格子最左边的一列,机器人不可能从某个位置向右走一步到达一个行号 j 为 0 的位置,因此,f(i, 0) 等于 1,即机器人只有一种方法可以到达坐标为 (i, 0) 的位置,即从 (i - 1, 0) 的位置向下走一步。
-
当行号 i、列号 j 都大于 0 时,机器人有两种方法可以到达坐标为 (i, j) 的位置。它既可以从坐标 (i - 1, j) 的位置向下走一步,也可以从坐标 (i, j - 1) 的位置向右走一步,因此,f(i, j) 等于 f(i - 1, j) 与 f(i, j - 1) 之和。
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for (int i = 1; i < m; ++i)
{
for (int j = 1; j < n; ++j)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
上述代码用一个二维数组 dp 保存 f(i, j) 的计算结果,f(i, j) 保存在 dp[i][j] 中。
上述代码的时间复杂度和空间复杂度都是 O(mn)。
优化空间效率:
接下来尝试优化代码的空间效率。在计算 f(i, j) 时只需要用到 f(i - 1, j) 和 f(i, j - 1) 的值,因此只需要保存标号分别为 i - 1 和 i 的两行就可以。如果创建一个只有两行的二维数组 dp,将 f(i, j) 保存在 dp[i % 2][j] 中,那么就将空间复杂度优化到 O(n)。
还可以进一步优化空间效率,只需要创建一个一维数组 dp 就可以。在计算 f(i, j) 时需要用到 f(i - 1, j) 和 f(i, j - 1) 的值。接下来在计算 f(i, j + 1) 时需要用到 f(i - 1, j + 1) 和 f(i, j) 的值。在计算完 f(i, j) 之后就不再需要 f(i - 1, j) 的值。在二维表格中,f(i, j) 和 f(i - 1, j) 是上下相邻的两个位置。由于在用 f(i - 1, j) 计算出 f(i, j) 之后就不再需要 f(i - 1, j),因此可以只用一个位置来保存 f(i - 1, j) 和 f(i, j) 的值。这个位置在计算 f(i, j) 之前保存的是 f(i - 1, j) 的值,计算 f(i, j) 之后保存的是 f(i, j) 的值。由于每个位置能够用来保存两个值,因此只需要一个一维数组就能保存表格中的两行。
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for (int i = 1; i < m; ++i)
{
for (int j = 1; j < n; ++j)
{
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
};
上述代码的时间复杂度仍然是 O(mn),但空间复杂度被优化到 O(n)。
面试题 99 : 最小路径之和
题目:
在一个 m x n(m、n 均大于 0)的格子中,每个位置都有一个数字。一个机器人每步只能向下或向右,请计算它从格子的左上角到达右下角的路径的数字之和的最小值。例如,从下图中 3 x 3 的格子的左上角到达右下角的路径的数字之和的最小值是 8,图中数字之和最小的路径用灰色背景表示。
分析:
和面试题 98 类似,机器人从格子的左上角到达右下角需要多步,每步都可能有向下或向右两个选择。由于这个题目并没有要求列出所有的路径,而是求出路径的数字之和的最小值,也就是求最优解,因此这个问题适合应用动态规划求解。
分析确定状态转移方程:
应用动态规划解决问题的关键在于找出状态转移方程。用函数 f(i, j) 表示从格子的左上角坐标为 (0, 0) 的位置(用 grid[0][0] 表示)出发到达坐标为 (i, j) 的位置(用 grid[i][j] 表示)的路径的数字之和的最小值。如果格子的大小为 m x n,那么 f(m - 1, n - 1) 就是问题的解。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][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)
{
dp[i][0] = dp[i - 1][0] + grid[i][0];
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];
}
};
上述代码用二维数组 dp 保存状态转移方程的计算结果,f(i, j) 保存在 dp[i][j] 中。
上述代码的时间复杂度和空间复杂度都是 O(mn)。
优化空间效率:
由于计算 f(i, j) 时只需要用到它上面一行的 f(i - 1, j),因此实际上只需要保存两行就可以。也就是说,创建一个只有两行的数组 dp,将 f(i, j) 保存到 dp[i % 2][j] 中即可。
还可以进一步优化空间效率,即只需要一个一维数组 dp。在计算 f(i, j) 时需要 f(i - 1, j) 的值。值得注意的是,f(i - 1, j) 在完成 f(i, j) 的计算之后再也用不到了,因此将 f(i - 1, j) 和 f(i, j) 保存到同一个数组 dp 的同一个位置 dp[j] 中。在计算 f(i, j) 之前,dp[j] 保存的是 f(i - 1, j) 的值,用 f(i - 1, j) 的值计算出 f(i, j) 的值之后,将 f(i, j) 的值保存到 dp[j] 中。虽然之前保存在 dp[j] 中的 f(i - 1, j) 的值被覆盖了,但这个值也不再需要,它被覆盖不会带来任何问题。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> dp(n);
dp[0] = grid[0][0];
for (int j = 1; j < n; ++j)
{
dp[j] = dp[j - 1] + grid[0][j];
}
for (int i = 1; i < m; ++i)
{
dp[0] += grid[i][0];
for (int j = 1; j < n; ++j)
{
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[n - 1];
}
};
优化之后的代码的时间复杂度仍然是 O(mn),但空间复杂度变成了 O(n)。
面试题 100 : 三角形中最小路径之和
题目:
在一个由数字组成的三角形中,第 1 行有 1 个数字,第 2 行有 2 个数字,以此类推,第 n 行有 n 个数字。例如,下图是一个包含 4 行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。如下图所示,从三角形顶部到底部的路径数字之和的最小值为 11,对应的路径经过的数字用阴影表示。
分析:
可能需要用矩阵坐标来定位三角形中的数字。上图中的相邻两行数字的位置相互交错,这样很难用矩阵坐标来表示数字的位置。可以移动三角形每行的位置使它们左端对齐,如下图所示。对齐之后就能很方便地用矩阵的行坐标和列坐标来定位每个数字。如果三角形有 n 行数字,将这些行左端对齐之后就成了一个 n x n 的矩阵和左下半部分。如果三角形中某个数字在矩阵中的行号和列号分别是 i 和 j,那么 i >= j。
在左端对齐的三角形中,从一个数字出发,下一步要么前往下一行正下方的数字,要么前往右下方的数字。例如,在上图的三角形中从顶部的数字 2 出发,可以前往第 2 行位于它正下方的数字 3,也可以前往右下方的数字 4。
如果一个三角形有多行,那么从它的顶部到底部需要多步,而且每步都面临两个选择。例如,在上图的三角形中,从顶部数字 2 出发,下一步既可能前往第 2 行的第 1 个数字 3,也可能前往第 2 行的第 2 个数字 4。解决一个问题需要多个步骤,而且每个步骤都面临多个选择,这看起来可以用回溯法解决。但这个题目并没有要求列出从顶部到底部的所有路径,而是要求计算路径之和的最小值,也就是求最优解。因此,动态规划更适合解决这个问题。
分析确定状态转移方程:
应用动态规划解决问题的关键在于确定状态转移方程。可以用 f(i, j) 表示从三角形的顶部出发到达行号和列号分别为 i 和 j(i >= j)的位置时路径数字之和的最小值,同时用 T[i][j] 表示三角形行号和列号分别为 i 和 j 的数字。如果三角形中包含 n 行数字,那么 f(n - 1, j) 的最小值就是整个问题的最优解。
-
f(0, 0) 等于 T[0][0]。
-
如果 j 等于 0,也就是当前到达某行的第 1 个数字。由于路径的每步都是前往正下方或右下方的数字,而此时当前位置的左上方没有数字,那么前一步一定是来自它的正上方的数字,因此 f(i, 0) 等于 f(i - 1, 0) 与 T[i][0] 之和(i > 0)。
-
如果 i 等于 j,也就是当前到达某行的最后一个数字,此时它的正上方没有数字,前一步只能是来自它左上方的数字,因此 f(i, j) 等于 f(i - 1, j - 1) 与 T[i][j] 之和(i > 0)。
-
如果当前行号和列号分别为 i 和 j 的位置位于某行的中间,那么前一步既可能是来自它正上方的数字(行号和列号分别为 i - 1 和 j),也可能是来自它左上方的数字(行号和列号分别为 i - 1 和 j - 1),所以 f(i, j) 等于 f(i - 1, j) 与 f(i - 1, j - 1) 的最小值再加上 T[i][j]。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(n));
dp[0][0] = triangle[0][0];
for (int i = 1; i < n; ++i)
{
for (int j = 0; j <= i; ++j)
{
dp[i][j] += triangle[i][j];
if (j == 0)
dp[i][j] += dp[i - 1][j];
else if (j == i)
dp[i][j] += dp[i - 1][j - 1];
else
dp[i][j] += min(dp[i - 1][j], dp[i - 1][j - 1]);
}
}
int result = INT_MAX;
for (int num : dp[n - 1])
{
result = min(result, num);
}
return result;
}
};
上述代码创建了一个 n x n(n 为三角形的行数)的二维数组 dp,但实际上只用到了数组的左下半部分。先用一个二重循环按照状态转移方程逐一计算 f(i, j) 的值并保存到 dp[i][j] 中,然后用一个 for 循环找出二维数组 dp 最后一行的最小值作为整个问题的最优解。
上述代码的时间复杂度和空间复杂度都是 O(n^2)。
优化空间效率:
由于计算 f(i, j) 时只需要用到它上面一行的 f(i - 1, j) 和 f(i - 1, j - 1),因此实际上只需要保留两行就可以。也就是说,创建一个只有两行的数组 dp,将 f(i, j) 保存到 dp[i % 2][j] 中即可。
还可以考虑进一步优化空间效率,即能否只需要一个一维数组 dp。如果能够将 f(i, j) 和 f(i - 1, j) 都保存到 dp[j] 中,那么一个一维数组就可以保存所需的数据。
假设在计算 f(i, j) 之前 dp[j] 中保存的是 f(i - 1, j) 的值。在计算 f(i, j) 时需要 f(i - 1, j - 1) 和 f(i - 1, j)。在计算完 f(i, j) 之后能否用 f(i, j) 的值覆盖保存在 dp[j] 中的 f(i - 1, j) 取决于是否还需要 f(i - 1, j) 的值。
-
如果每行按照从左到右的顺序,那么在计算完 f(i, j) 之后将计算 f(i, j + 1),而计算 f(i, j + 1) 可能需要 f(i - 1, j) 和 f(i - 1, j + 1) 的值,也就是 f(i - 1, j) 的值在计算 f(i, j + 1) 时可能会被用到,因此在计算完 f(i, j) 之后不能将 f(i - 1, j) 的值丢掉。
-
但计算 f(i, j) 时并不依赖同一行左侧的 f(i, j - 1),因此并不一定要按照从左到右的顺序计算每行,按照从右到左的顺序计算也可以。如果按照从右到左的顺序,则先计算 f(i, j),需要用到 f(i - 1, j - 1) 和 f(i - 1, j)。接下来计算 f(i, j - 1),需要用到 f(i - 1, j - 2) 和 f(i - 1, j - 1)。计算 f(i - 1, j - 1) 并不需要用到 f(i - 1, j)。因此,按照从右到左的顺序在计算完 f(i, j) 之后,将 f(i, j) 的值保存到 dp[j] 中并替换 f(i - 1, j) 的值,并且不会带来任何问题,因此 f(i - 1, j) 的值以后就不再需要。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> dp(n);
dp[0] = triangle[0][0];
for (int i = 1; i < n; ++i)
{
for (int j = i; j >= 0; --j)
{
if (j == i)
dp[j] = dp[j - 1] + triangle[i][j];
else if (j == 0)
dp[j] += triangle[i][j];
else
dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j];
}
}
int result = INT_MAX;
for (int num : dp)
{
result = min(result, num);
}
return result;
}
};
上述代码的时间复杂度仍然是 O(n^2),但空间复杂度变成了 O(n)。