牛客題霸 [矩陣的最小路徑和] C++題解/答案、

題目描述

給定一個 n * m 的矩陣 a，從左上角開始每次只能向右或者向下走，最后到達右下角的位置，路徑上所有的數字累加起來就是路徑和，輸出所有的路徑中最小的路徑和。

題解：

dp[i]:表示到達第i行所需要的的最短路徑
對于第一列，只能從上往下
對于第一行，只能從左往右
對于非第一行第一列的位置，到達有兩個辦法，從該點的左側過來或者從上側過來，取最小即可，然后加當前值

代碼：

class Solution { public:/*** * @param matrix int整型vector<vector<>> the matrix* @return int整型*/int minPathSum(vector<vector<int> >& matrix) {// write code hereint m=matrix.size();//列int n=matrix[0].size();//行vector<int>dp(n);dp[0]=matrix[0][0];for(int j=1;j<n;j++){dp[j]=dp[j-1]+matrix[0][j];//求出第一列的前綴和}for(int i=1;i<m;i++){dp[0]+=matrix[i][0];for(int j=1;j<n;j++){dp[j]=min(dp[j-1],dp[j])+matrix[i][j];}}return dp[n-1];} };

總結

以上是生活随笔為你收集整理的牛客题霸 [矩阵的最小路径和] C++题解/答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。