NC59矩阵的最小路径和（四种语言+视频讲解）

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=196&&tqId=37157&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking

-3、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-5、代码：
c++版本:

class Solution
{
public:
    /**
     *
     * @param matrix int整型vector<vector<>&gt; the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> &gt;&amp; matrix)
    {
        // write code here
        int n = matrix.size(); //matrix的行
        int m = matrix[0].size();//matrix的列
        int dp[n + 10][m + 10];//dp[i][j]代表在第i行第j列最小的路径和为多少
        dp[0][0] = matrix[0][0];//初始化dp[0][0]为matrix[0][0]
        for(int i = 1; i &lt; n; i ++)
        {
            dp[i][0] = dp[i-1][0] +  matrix[i][0];//初始化dp[i][0]
        }
        for(int i = 1; i &lt; m; i ++)
        {
            dp[0][i] = dp[0][i-1] +  matrix[0][i];//初始化dp[0][i]
        }
        for (int i = 1; i &lt; n; i++)
        {
            for (int j = 1; j &lt; m; j++)
            {
                //dp[i][j] 就应该等于在dp[i - 1][j]、dp[i][j - 1]选一个最小的在和matrix[i][j]加和
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }
        return dp[n - 1][m - 1];//最终的结果为dp[n-1][m-1]即二维表的最右下角
    }
};

Java版本：

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int n = matrix.length; //matrix的行
        int m = matrix[0].length;//matrix的列
        int [][]dp = new int[n + 10][m + 10];//dp[i][j]代表在第i行第j列最小的路径和为多少
        dp[0][0] = matrix[0][0];//初始化dp[0][0]为matrix[0][0]
        for(int i = 1; i < n; i ++)
        {
            dp[i][0] = dp[i-1][0] +  matrix[i][0];//初始化dp[i][0]
        }
        for(int i = 1; i < m; i ++)
        {
            dp[0][i] = dp[0][i-1] +  matrix[0][i];//初始化dp[0][i]
        }
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < m; j++)
            {
                //dp[i][j] 就应该等于在dp[i - 1][j]、dp[i][j - 1]选一个最小的在和matrix[i][j]加和
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }
        return dp[n - 1][m - 1];//最终的结果为dp[n-1][m-1]即二维表的最右下角
    }
}

Python版本:

#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix ):
        # write code here
        n = len(matrix)#matrix的行
        m = len(matrix[0])#matrix的列
        dp = [[0] * (m+10) for _ in range(n+10)]#dp[i][j]代表在第i行第j列最小的路径和为多少
        dp[0][0] = matrix[0][0];#初始化dp[0][0]为matrix[0][0]
        for i in range(1,n):
            dp[i][0] = dp[i-1][0] +  matrix[i][0]#初始化dp[i][0]
        for i in range(1,m):
            dp[0][i] = dp[0][i-1] +  matrix[0][i];#初始化dp[0][i]
        for i in range(1,n):
            for j in range(1,m):
            #dp[i][j] 就应该等于在dp[i - 1][j]、dp[i][j - 1]选一个最小的在和matrix[i][j]加和
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]

        return dp[n - 1][m - 1] #最终的结果为dp[n-1][m-1]即二维表的最右下角

JavaScript版本：

/**
 * 
 * @param matrix int整型二维数组 the matrix
 * @return int整型
 */
function minPathSum( matrix ) {
    // write code here
    let n = matrix.length; //matrix的行
    let m = matrix[0].length;//matrix的列
    let dp = Array.from(new Array(n),() => new Array(m).fill(0));//dp[i][j]代表在第i行第j列最小的路径和为多少
    dp[0][0] = matrix[0][0];//初始化dp[0][0]为matrix[0][0]
    for(let i = 1; i < n; i ++)
    {
        dp[i][0] = dp[i-1][0] +  matrix[i][0];//初始化dp[i][0]
    }
    for(let i = 1; i < m; i ++)
    {
        dp[0][i] = dp[0][i-1] +  matrix[0][i];//初始化dp[0][i]
    }
    for (let i = 1; i < n; i++)
    {
        for (let j = 1; j < m; j++)
        {
            //dp[i][j] 就应该等于在dp[i - 1][j]、dp[i][j - 1]选一个最小的在和matrix[i][j]加和
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
        }
    }
    return dp[n - 1][m - 1];//最终的结果为dp[n-1][m-1]即二维表的最右下角
}
module.exports = {
    minPathSum : minPathSum
};