題目（鏈接）
給定一個包含非負整數的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] <= 100
題解
思路：
- 動態規劃
- 特判第一個位置
- 如果某個位置在第一行，那么只能從左面走過來，不能從上面走過來；如果某個位置在第一列，那么只能從上面走過來，不能從左面走過來，除此以外的點均是從上面走過來或者從左面走過來，
- 從上面走過來：
dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j]) - 從左面走過來：
dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j])
code:
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
const int N = 210, INF = 1e9;
int dp[N][N];
for (int i = 0; i < n; i ++){
for (int j = 0; j < m; j ++){
// 特判第一個位置
if (i == 0 && j == 0){
dp[i][j] = grid[i][j];
} else {
dp[i][j] = INF;
// 特判第一行
if (i > 0){
dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j]);
}
// 特判第一列
if (j > 0){
dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j]);
}
}
}
}
return dp[n - 1][m - 1];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/505522.html
標籤：其他
下一篇：cmake 入門筆記