目錄
1289. 下降路徑最小和 II
題目描述：
實現(xiàn)代碼與解析：
動態(tài)規(guī)劃
原理思路：
1289. 下降路徑最小和 II
題目描述：
????????給你一個?n x n?整數(shù)矩陣?grid?，請你返回?非零偏移下降路徑?數(shù)字和的最小值。
非零偏移下降路徑?定義為：從?grid?數(shù)組中的每一行選擇一個數(shù)字，且按順序選出來的數(shù)字中，相鄰數(shù)字不在原數(shù)組的同一列。
示例 1：
輸入：grid = [[1,2,3],[4,5,6],[7,8,9]] 輸出：13 解釋： 所有非零偏移下降路徑包括： [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] 下降路徑中數(shù)字和最小的是?[1,5,7] ，所以答案是?13 。
示例 2：
輸入：grid = [[7]] 輸出：7
提示：
n == grid.length == grid[i].length1 <= n <= 200-99 <= grid[i][j] <= 99
實現(xiàn)代碼與解析：
動態(tài)規(guī)劃
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> f(n,vector<int>(m, 0x3f3f3f3f));
for (int i = 0; i < m; i++)
f[0][i] = grid[0][i];
for (int i = 1; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < m; k++)
{
if (j == k) continue;
f[i][j] = min(f[i][j], f[i - 1][k] + grid[i][j]);
}
int res = 0x3f3f3f3f;
for (int i = 0; i < m; i++)
res = min(res, f[n - 1][i]);
// for (int i = 0; i < n; i++)
// {
// for (int j = 0; j < m; j++)
// {
// cout << f[i][j] << " ";
// }
// cout << endl;
// }
return res;
}
};原理思路：
? ? ? ? 頂多中等題，難度不應該標困難。文章來源：http://www.zghlxwxcb.cn/news/detail-646997.html
? ? ? ? 動態(tài)規(guī)劃，dp數(shù)組含義就是到以下標 i， j 為結尾的最小值。數(shù)據(jù)量很小，其實就是三重暴力循環(huán)而已。?文章來源地址http://www.zghlxwxcb.cn/news/detail-646997.html
到了這里，關于Leetcode每日一題：1289. 下降路徑最小和 II（2023.8.10 C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
