题解 | BM68 矩阵的最小路径和

/**
 * 
 * @param matrix int整型二维数组 the matrix
 * @return int整型
 */
function minPathSum(matrix) {
    // write code here
    let m = matrix.length;
    if (m < 1) {
        return 0;
    }
    let n = matrix[0].length;
    let ans = [];
    for (let i = 0; i <= m; i++) {
        ans.push([]);
        for (let j = 0; j <= n; j++) {
            ans[i].push(1000007);
        }
    }
    // 给ans[1][0]赋值也可以。因为一开始第一个点必须有一个是0，否则循环初始值不对
    ans[0][1] = 0;
    // 思路就是i，j节点的最小路径和等于上面（i-1，j）路径，左边（i，j-1）路径中小的那一个加上当前节点的花费
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            ans[i][j] = Math.min(ans[i - 1][j], ans[i][j - 1]) + matrix[i - 1][j - 1];
        }
    }
    console.log(ans)
    return ans[m][n];
}
module.exports = {
    minPathSum: minPathSum
};