LeetCode 120. 三角形最小路径和Rust 实现思路动态规划自底向上从倒数第二行开始向上递推。对于位置 (i, j)它只能从下一行的 (i1, j) 或 (i1, j1) 走上来因此triangle[i][j] min(triangle[i1][j], triangle[i1][j1])一路推到顶部triangle[0][0] 即为最小路径和。如果不想修改原数组可以用一个一维 dp 数组保存下一行的结果空间复杂度降为 O(n)。Rust 实现一维 DP不修改原数组implSolution{pubfnminimum_total(triangle:VecVeci32)-i32{iftriangle.is_empty(){return0;}// dp 初始化为最后一行的副本letmutdptriangle.last().unwrap().clone();// 从倒数第二行向上遍历foriin(0..triangle.len()-1).rev(){forjin0..triangle[i].len(){dp[j]triangle[i][j]dp[j].min(dp[j1]);}}dp[0]}}Rust 实现原地修改空间 O(1)implSolution{pubfnminimum_total(muttriangle:VecVeci32)-i32{iftriangle.is_empty(){return0;}// 从倒数第二行开始向上累加foriin(0..triangle.len()-1).rev(){forjin0..triangle[i].len(){triangle[i][j]triangle[i1][j].min(triangle[i1][j1]);}}triangle[0][0]}}关键点自底向上避免处理边界和初始化问题最后直接返回顶部。状态转移dp[j] triangle[i][j] min(dp[j], dp[j1])。空间优化一维 dp 在计算当前行时只依赖下一行因此可以原地覆盖。Rust 注意triangle.last().unwrap().clone() 获取最后一行的副本(0…triangle.len() - 1).rev() 用于从倒数第二行向上遍历i32::min 方法可直接调用。复杂度· 时间O(n^2)n 为三角形行数每个元素访问一次。· 空间一维 DP 法 O(n)原地修改法 O(1)不计输入本身。测试用例#[test]fntest_minimum_total(){assert_eq!(Solution::minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]]),11);assert_eq!(Solution::minimum_total(vec![vec![-10]]),-10);assert_eq!(Solution::minimum_total(vec![vec![-1],vec![2,3],vec![1,-1,-3]]),-1);}
