- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
状态定义
dp[i][j] 代表从 (0, 0) 走到 (i, j) 的最小路径和。
状态转移方程
明确题意：只能向右或者向下走，也就是说终点 (i, j) 只能从 (i - 1, j) 或者 (i, j - 1) 走过来。
分为以下三种情况分别处理：
- 左边或者上边都是边界时，终点也就是起点。
dp[i][j] = grid[i][j]
- 左边或者上边为边界时：
grid[i][j] = grid[i - 1][j] + grid[i][j]grid[i][j] = grid[i][j - 1] + grid[i][j]
- 左边和上边都不为边界时：
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
constminPathSum=function(grid){constn=grid.lengthconstm=grid[0].lengthconstdp=Array.from(newArray(n),()=>newArray(m))for(leti=0;i<n;i++){for(letj=0;j<m;j++){if(i!==0&&j!==0){dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]}elseif(i!==0&&j===0){dp[i][j]=dp[i-1][j]+grid[i][j]}elseif(i===0&&j!==0){dp[i][j]=dp[i][j-1]+grid[i][j]}elseif(i===0&&j===0){dp[i][j]=grid[i][j]}}}returndp[n-1][m-1]}
- 时间复杂度: O(m * n)
- 空间复杂度: O(m * n)
降维
不需要额外建立空间，直接遍历修改grid[i][j]。
constminPathSum=function(grid){constn=grid.lengthconstm=grid[0].lengthfor(leti=0;i<n;i++){for(letj=0;j<m;j++){if(i!==0&&j!==0){grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j]}elseif(i!==0&&j===0){grid[i][j]=grid[i-1][j]+grid[i][j]}elseif(i===0&&j!==0){grid[i][j]=grid[i][j-1]+grid[i][j]}elseif(i===0&&j===0){grid[i][j]=grid[i][j]}}}returngrid[n-1][m-1]}
- 时间复杂度: O(m * n)
- 空间复杂度: O(1)