苏州网页服务开发与网站建设,俱乐部网站模板,西安房产网,在线crm在线oa免费文章目录 写在前面Tag题目来源解题思路方法一#xff1a;动态规划方法二#xff1a;空间优化 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题… 文章目录 写在前面Tag题目来源解题思路方法一动态规划方法二空间优化 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【动态规划-空间优化】【数组】 题目来源
64. 最小路径和 解题思路
方法一动态规划
定义状态
朴素的动态规划方法是定义状态 dp[i][j]表示从网格左上角 (0, 0) 位置到 (i, j) 位置的最小路径和。
状态转移
根据题目中 “每次只能向下或者向右移动一步”可知到达位置 (i, j) 只能从 (i-1, j) 向下移动一步或者从 (i, j-1) 向右一步因此有转移关系 d p [ i ] [ j ] m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) , i ≥ 1 , j ≥ 1 dp[i][j] min(dp[i-1][j], dp[i][j-1]), i \ge 1, j \ge 1 dp[i][j]min(dp[i−1][j],dp[i][j−1]),i≥1,j≥1
base case
dp[0][0] grid[0][0]。
对于网格 grid 中的第一行和第一列位置只能从对应位置的左侧和上方的位置移动一步得到于是需要进行如下方式的初始化
// 第一列
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[0][j] dp[0][j - 1] grid[0][j];
}最后返回
dp[m-1][n-1] 表示从网格左上角到网格右下角的最小路径和。
实现代码
class Solution {
public:int minPathSum(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint dp vectorvectorint(m, vectorint(n));dp[0][0] grid[0][0];// 对于在第一行或者第一列第一列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[0][j] dp[0][j - 1] grid[0][j];}// 对于不在第一行和第一列的元素for (int i 1; i m; i) {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];}
};复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn) m m m 为网格 grid 的行数 n n n 为网格的列数。
空间复杂度 O ( m n ) O(mn) O(mn)。
方法二空间优化
方法一中朴素解法的空间复杂度可以进行优化只需要使用 O ( m i n { m , n } ) O(min\{m, n\}) O(min{m,n}) 的复杂度即可解决。
我们以 示例 1 为例说明如何使用线性空间解决本题。
网格的行数和列数一样选择按行来更新最小路径和选择列也可以维护一个数组 dp 长度为 3。
初始化 dp {1, 4, 5}dp[0] 表示从位置 (0, 0) 到位置 (0, 0) 的最小路径和dp[1] 表示从位置 (0, 0) 到位置 (0, 1) 的最小路径和dp[2] 表示从位置 (0, 0) 到位置 (0, 2) 的最小路径和。
在网格的第一行从 0 开始数dp[0] 表示从位置 (0, 0) 到位置 (1, 0) 的最小路径和因为只能从 (0, 0) 位置到 (1, 0) 位置所以更新 dp[0] dp[0] grid[1][0]dp[1] 表示从位置 (0, 0) 到位置 (1, 1) 的最小路径和因为可以从 (1, 0) 位置向右或者 (0, 1) 位置向下移动到位置 (1, 1)所以有 dp[1] min(dp[0], dp[1]) grid[i][j]…
具体实现见如下代码。
实现代码
class Solution {
public:int minPathSum(vectorvectorint grid) {int m grid.size();int n grid[0].size();int more max(m, n);int less min(m, n);bool rowMore more m; // 判断是否是行数大于等于列数vectorint arr(less); // 以较短维度的长度作为临时空间比如列数较小int i, j;for (i 0; i less; i) {// 更新第 0 行的所有列即初始化if (i 0) {arr[i] grid[0][0];}else {arr[i] arr[i - 1] (rowMore ? grid[0][i] : grid[i][0]);}}for (i 1; i more; i) {// 按照行进行更新arr[0] arr[0] (rowMore ? grid[i][0] : grid[0][i]); // 更新 i 行 0 列的答案for (j 1; j less; j) { // 更新 i 行其他列的答案arr[j] min(arr[j - 1], arr[j]) (rowMore ? grid[i][j] : grid[j][i]);}}return arr[less-1];}
};复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn) m m m 为网格 grid 的行数 n n n 为网格的列数。
空间复杂度 O ( m i n { m , n } ) O(min\{m, n\}) O(min{m,n})。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
