LeetCode 64「最小路径和」的 Rust 实现同样提供原地修改和一维滚动数组两个版本。思路dp[i][j]表示走到(i, j)的最小路径和转移方程dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])原地修改版推荐O(1) 额外空间implSolution{pubfnmin_path_sum(grid:VecVeci32)-i32{letmutgridgrid;let(m,n)(grid.len(),grid[0].len());// 第一行只能从左向右累加forjin1..n{grid[0][j]grid[0][j-1];}// 第一列只能从上向下累加foriin1..m{grid[i][0]grid[i-1][0];}foriin1..m{forjin1..n{grid[i][j]grid[i-1][j].min(grid[i][j-1]);}}grid[m-1][n-1]}}一维滚动数组版不修改输入implSolution{pubfnmin_path_sum(grid:VecVeci32)-i32{letngrid[0].len();letmutdpvec![i32::MAX;n];dp[0]0;forrowingrid{dp[0]row[0];forjin1..n{dp[j]row[j]dp[j].min(dp[j-1]);}}dp[n-1]}}复杂度两个版本均为时间 O(m×n)原地版额外空间 O(1)滚动数组版 O(n)。几个 Rust 细节参数是不可变的VecVeci32用let mut grid grid;遮蔽shadowing后原地修改避免多余拷贝组合数1 m, n 200且数值非负最大路径和不超过200 * 200 * 100 4,000,000i32不会溢出
