网站开发专业公司有哪些,龙岗高端网站建设,做团购的家居网站有哪些,著名网站设计师目录
前言
面试题 98 : 路径的数目
面试题 99 : 最小路径之和
面试题 100 : 三角形中最小路径之和 前言
矩阵路径是一类常见的可以用动态规划来解决的问题。这类问题通常输入的是一个二维的格子#xff0c;一个机器人按照一定的规则从格子的某个位置走到另一个位置#…目录
前言
面试题 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) {vectorvectorint dp(m, vectorint(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) {vectorint 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 nm、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(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint dp(m, vectorint(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(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorint 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 和 ji 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(vectorvectorint triangle) {int n triangle.size();vectorvectorint dp(n, vectorint(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];elsedp[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 nn 为三角形的行数的二维数组 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(vectorvectorint triangle) {int n triangle.size();vectorint 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];elsedp[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)。
