三角形最小路径和

[pwstrick]

120. 三角形最小路径和

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    const len = triangle.length;
    if(len == 0)
        return 0;
    let dp = [triangle[0]],     //初始化dp
        i, j;
    for(i=1; i<len; i++) {
        dp[i] = [dp[i-1][0]+triangle[i][0]];        //初始化第一列
        for(j=1, curLen=triangle[i].length; j<curLen; j++) {
            if(dp[i-1][j] === undefined) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];       //特殊情况
            }else {
                dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];     //状态转移方程
            }

        }
    }
    return Math.min.apply(this, dp[i-1]);
};