NC59矩阵的最小路径和

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、 设计思想：

详细操作流程看下图：

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

class Solution
{
public:
    /**
     *
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& 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 < 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] = 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