一、題目解析

從左上角到右下角使得數字總和最小且只能向下或向右移動

二、算法原理

1.狀態表示

我們需要求到達[i,j]位置時數字總和的最小值，所以dp[i][j]表示：到達[i,j]位置時，路徑數字總和的最小值。

2.狀態轉移方程

?

到達[i,j]之前要先到達[i-1,j]或[i,j-1]位置，比較得出最小值然后加上grid[i][j]的值

3.初始化

?

4.填表順序

從左往右，從上到下

5.返回值

返回dp[m][n]

建議自己上手實現一下，鏈接：64. 最小路徑和 - 力扣（LeetCode）?

三、代碼示例

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));dp[0][1] = dp[1][0] = 0;for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++){dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];}}return dp[m][n];}
};

?

?看到最后，如果對您有所幫助還請點贊、收藏、關注，點點關注不迷路，我們下期再見！