题解 | 三角形最小路径和
三角形最小路径和
https://www.nowcoder.com/practice/c9d44b73dc7c4dbfa4272224b1f9b42c
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型二维数组
* @return int整型
*/
export function minTrace(triangle: number[][]): number {
// write code here
const n = triangle.length;
// 初始化 dp 数组为最后一行的值
let dp = [...triangle[n - 1]];
// 从倒数第二行开始向上计算
for (let i = n - 2; i >= 0; i--) {
for (let j = 0; j < triangle[i].length; j++) {
dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
}
}
// 返回顶部的最小路径和
return dp[0];
}
Momenta公司福利 594人发布
投递字节跳动等公司8个岗位
查看30道真题和解析