給定一個包含非負整數的 m x n 網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

說明：每次只能向下或者向右移動一步。

數據范圍：
n <= 100,m <= 100;

輸入：
3 3
1 3 1
1 5 1
4 2 1
輸出：
7

這樣走，路徑上的數字總和為最小

解題思路：
我們首先定義dp[i][j]表示從左上角到(i,j)這個點的路徑上的數字的最小總和，現在我們很容易想到關系表達式為:

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j]; //表示從上一步路徑數字最小總和+這個點的數字，結果為從左上角到這個點的路徑最小數字和

然后我們思考如何初始化，如果i = 0,i-1就是-1,數組就會越界，也很容易想到怎么初始化：

dp[0][0] = a[0][0];for (int i = 1; i < n; i++) {dp[i][0] = dp[i - 1][0] + a[i][0];}for (int i = 1; i < m; i++) {dp[0][i] = dp[0][i - 1] + a[0][i];}

代碼如下：

#include <iostream> using namespace std; const int N = 110; int a[N][N]; int dp[N][N];int main() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {cin >> a[i][j];}dp[0][0] = a[0][0];for (int i = 1; i < n; i++) {dp[i][0] = dp[i - 1][0] + a[i][0];}for (int i = 1; i < m; i++) {dp[0][i] = dp[0][i - 1] + a[0][i];}for (int i = 1; i < n; i++)for (int j = 1; j < m; j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];}cout << dp[n - 1][m - 1] << endl;return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的网格路径最小数字和的全部內容，希望文章能夠幫你解決所遇到的問題。

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