题解 | #三角形最小路径和#

前端初学者，刚学动态规划的代码（较为繁琐）

• dp[i][j]表示以i,j位置的点为起点到达最低端的最小路径和。
• 状态方程： dp[i][j] = min(triangle[i][j]+dp[i+1][j],triangle[i][j]+dp[i+1][j+1])
• 边界条件：dp[n - 1][i] = triangle[n - 1][i];（三角形最下面一行）
• dp[0][0]即为所求

function minTrace( triangle ) {
    // write code here
    if(triangle.length == 0 || !triangle) return 0
    let n = triangle.length;
    //创建二维数组
    let dp = new Array(n);
    for(let i = 0; i< n; i++){
        let len = triangle[i].length
        dp[i] = new Array(len);
    }
    for(let i = 0; i< n; i++){
        dp[n - 1][i] = triangle[n - 1][i];
    }
    for(let i = n -2; i>= 0; i--){
        for(let j = 0; j< triangle[i].length; j++){
            dp[i][j] = Math.min(triangle[i][j]+dp[i+1][j],triangle[i][j]+dp[i+1][j+1])
        }
    }
    return dp[0][0]
    
}
module.exports = {
    minTrace : minTrace
};