题解 | 三角形最小路径和

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @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];
}