資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最小下降路徑和 II
假設我們有一個網格 arr，這是一個正方形網格，一條具有非零偏移量的下降路徑是從 arr 的每一行中精確選擇一個元素，使得在相鄰行中選擇的兩個元素不在同一列。我們必須找到具有非零偏移量的下降路徑的最小和。
因此，如果輸入類似於 arr 類似於 [[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]。現在，和最小的下降路徑是 [1,5,7]，因此答案是 13。
為了解決這個問題，我們將遵循以下步驟 -
n := 行數，m := 列數
初始化 i := 1，當 i < n 時，更新（i 加 1），執行 -
定義大小為 m 的陣列 leftMin 和 rightMin
leftMin[0] := arr[i - 1, 0]
初始化 j := 1，當 j < m 時，更新（j 加 1），執行 -
leftMin[j] := leftMin[j - 1] 和 arr[i - 1, j] 的最小值
rightMin[m - 1] = arr[i - 1, m - 1]
初始化 j := m - 2，當 j >= 0 時，更新（j 減 1），執行 -
rightMin[j] := arr[i - 1, j] 和 rightMin[j + 1] 的最小值
初始化 j := 0，當 j < m 時，更新（j 加 1），執行 -
leftVal := （如果 (j - 1) >= 0，則 leftMin[j - 1]，否則 1000000）
rightVal := （如果 (j + 1) < m，則 rightMin[j + 1]，否則 1000000）
arr[i, j] := arr[i, j] + min(leftVal, rightVal)
ans := inf
初始化 i := 0，當 i < m 時，更新（i 加 1），執行 -
ans := ans 和 arr[n - 1, i] 的最小值
返回 ans
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
int dp[10005][205];
class Solution {
public:
void pre(){
for(int i = 0; i <= 10000; i++){
for(int j = 0; j <=204; j++){
dp[i][j] = -1;
}
}
}
int minFallingPathSum(vector<vector<int>>& arr) {
int n = arr.size();
int m = arr[0].size();
for (int i = 1; i < n; i++) {
vector<int> leftMin(m);
vector<int> rightMin(m);
leftMin[0] = arr[i - 1][0];
for (int j = 1; j < m; j++) {
leftMin[j] = min(leftMin[j - 1], arr[i - 1][j]);
}
rightMin[m - 1] = arr[i - 1][m - 1];
for (int j = m - 2; j >= 0; j--) {
rightMin[j] = min(arr[i - 1][j], rightMin[j + 1]);
}
for (int j = 0; j < m; j++) {
int leftVal = (j - 1) >= 0 ? leftMin[j - 1] :
1000000;
int rightVal = (j + 1) < m ? rightMin[j + 1] :
1000000;
arr[i][j] += min(leftVal, rightVal);
}
}
int ans = INT_MAX;
for (int i = 0; i < m; i++)
ans = min(ans, arr[n - 1][i]);
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
cout << (ob.minFallingPathSum(v));
}輸入
{{1,2,3},{4,5,6},{7,8,9}}輸出
13
232 次檢視
