Kimi LeetCode 63. 不同路径 II Rust实现

LeetCode 63. 不同路径 II — Rust 实现解法一一维 DP推荐dp[j]表示当前行第j列的路径数与 Python 解法二思路相同implSolution{pubfnunique_paths_with_obstacles(obstacle_grid:VecVeci32)-i32{letnobstacle_grid[0].len();letmutdpvec![0i64;n];dp[0]1;forrowinobstacle_grid{forjin0..n{ifrow[j]1{dp[j]0;}elseifj0{dp[j]dp[j-1];}}}dp[n-1]asi32}}解法二原地 DPO(1) 额外空间直接复用输入数组把每个格子原地改写为到达它的路径数implSolution{pubfnunique_paths_with_obstacles(mutobstacle_grid:VecVeci32)-i32{letmobstacle_grid.len();letnobstacle_grid[0].len();ifobstacle_grid[0][0]1{return0;}obstacle_grid[0][0]1;// 初始化第一列障碍之前为 1之后全为 0foriin1..m{obstacle_grid[i][0](obstacle_grid[i][0]0obstacle_grid[i-1][0]1)asi32;}// 初始化第一行forjin1..n{obstacle_grid[0][j](obstacle_grid[0][j]0obstacle_grid[0][j-1]1)asi32;}foriin1..m{forjin1..n{obstacle_grid[i][j]ifobstacle_grid[i][j]1{0}else{obstacle_grid[i-1][j]obstacle_grid[i][j-1]};}}obstacle_grid[m-1][n-1]}}说明类型选择解法一中dp用i64更稳妥题目数据范围内i32也够用m、n ≤ 100 时最大路径数约 2.3×10⁵⁸ 其实超出 i64……实际 LeetCode 63 官方约束答案在 i32 范围内评测用i64再as i32是常见的安全折中若想严格处理大数可用u128或num-bigint但不必要。注意点Rust 中bool as i32可直接得到 0/1解法二借此简化初始化。起点有障碍时直接返回 0。每行第一个格子j 0只依赖上一行的值天然继承无需特判。复杂度两种解法时间均为 O(m×n)解法一空间 O(n)解法二空间 O(1)。推荐解法一简洁不易出错。