題目描述：

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

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

輸入輸出樣例：

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因為路徑 1→3→1→1→1 的總和最小。

示例 2：
輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

提示：
m== grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

題解：

解題思路：

思路一（多維動態規劃）：

1、題目要求每次只能向下或者向右移動一步。則一個位置的元素可由左方和上方的位置移動而來。

• dp[ i ][ j ]為路徑上的數字總和最小。
• dp[ i ][ j ] = min(dp[ i-1 ][ j ],dp[ i ][ j-1 ])+grid[ i ][ j ]。
• dp[ 0 ][ 0 ] = grid[ 0 ][ 0 ]。
• dp[ 0 ][ j ] = dp[ 0 ][ j-1 ]+grid[ 0 ][ j ]。第一行的元素只能由左側元素移動得來。
• dp[ i ][ 0 ] = dp[ i-1 ][ 0 ]+grid[ 0 ][ j ]。第一列的元素只能由上側元素移動得來。

2、復雜度分析：
① 時間復雜度：O(mn)，其中 m 和 n 分別是網格的行數和列數。需要對整個網格遍歷一次，計算 dp 的每個元素的值。
② 空間復雜度：O(mn)，其中 m 和 n 分別是網格的行數和列數。創建一個二維數組 dp，和網格大小相同(也可使用一維dp數組：參考LeetCode 熱題 100_不同路徑（91_62_中等_C++）)。

代碼實現

代碼實現（思路一（多維動態規劃））：

class Solution {
public:// 計算從左上角到右下角的最小路徑和int minPathSum(vector<vector<int>>& grid) {// 創建一個dp數組，用于存儲從起點到達每個格子的最小路徑和vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));// 初始化dp數組的起始位置，起點的路徑和就是grid[0][0]的值dp[0][0] = grid[0][0];// 處理第一行，從左到右累加// 因為只能從左邊的格子走到當前格子，所以每一行的第一個格子的路徑和是累加的for (int j = 1; j < grid[0].size(); j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}// 處理第一列，從上到下累加// 因為只能從上方的格子走到當前格子，所以每一列的第一個格子的路徑和是累加的for (int i = 1; i < grid.size(); i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}// 從(1, 1)開始，遍歷整個grid// 每個格子的最小路徑和是從它的上方格子或者左方格子中選擇較小的路徑和，再加上當前格子的值for (int i = 1; i < grid.size(); i++) {for (int j = 1; j < grid[0].size(); j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}// 返回右下角的最小路徑和，即dp數組的右下角元素return dp[grid.size() - 1][grid[0].size() - 1];}
};

以思路一為例進行調試

#include<iostream>
#include<vector>
using namespace std;class Solution {
public:// 計算從左上角到右下角的最小路徑和int minPathSum(vector<vector<int>>& grid) {// 創建一個dp數組，用于存儲從起點到達每個格子的最小路徑和vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));// 初始化dp數組的起始位置，起點的路徑和就是grid[0][0]的值dp[0][0] = grid[0][0];// 處理第一行，從左到右累加// 因為只能從左邊的格子走到當前格子，所以每一行的第一個格子的路徑和是累加的for (int j = 1; j < grid[0].size(); j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}// 處理第一列，從上到下累加// 因為只能從上方的格子走到當前格子，所以每一列的第一個格子的路徑和是累加的for (int i = 1; i < grid.size(); i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}// 從(1, 1)開始，遍歷整個grid// 每個格子的最小路徑和是從它的上方格子或者左方格子中選擇較小的路徑和，再加上當前格子的值for (int i = 1; i < grid.size(); i++) {for (int j = 1; j < grid[0].size(); j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}// 返回右下角的最小路徑和，即dp數組的右下角元素return dp[grid.size() - 1][grid[0].size() - 1];}
};int main(int argc, char const *argv[])
{vector<vector<int>> grid={{1,3,1},{1,5,1},{4,2,1}};Solution s;cout<<s.minPathSum(grid);return 0;
}

LeetCode 熱題 100_最小路徑和（92_64)原題鏈接
歡迎大家和我溝通交流(????)