minPathSum

最小路径和 - 在网格中找到从左上角到右下角的最小路径和。

输入网格

网格数据 (每行用逗号分隔，行之间换行)1,3,1 1,5,1 4,2,1

执行过程

步骤 1 / 10

初始化起点 dp[0][0] = 1

1

1

3

1

1

5

1

4

2

1

速度:慢速正常快速超快

当前单元格

来源单元格

算法说明

最小路径和：从左上角到右下角，每次只能向下或向右移动。使用动态规划，dp[i][j]表示到达(i,j)的最小路径和。时间复杂度O(m×n)。

函数签名

function minPathSum(grid: number[][]): number
function minPathSumOptimized(grid: number[][]): number

参数

参数名	类型	必填	说明
grid	number[][]	是	m×n的二维网格

返回值

类型	说明
number	最小路径和

工作原理

1. DP定义: dp[i][j]表示从(0,0)到(i,j)的最小路径和
2. 初始化:
   • dp[0][0] = grid[0][0]
   • 第一行: 只能从左边来
   • 第一列: 只能从上边来
3. 状态转移: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
4. 返回结果: dp[m-1][n-1]

优化: 使用一维数组,空间复杂度降至O(n)

时间复杂度: O(m×n)
空间复杂度: O(m×n) 或 O(n)优化版