資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最小下降路徑和
假設我們有一個整數的方形陣列 A，我們想要找到透過 A 的最小下降路徑和。下降路徑基本上是從第一行中的任何元素開始的路徑，並從每一行中選擇一個元素。並且下一行的元素必須位於與前一行的列最多相差一的列中。所以如果矩陣是這樣的：
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
那麼輸出是 12。有幾個不同的下降路徑。它們是 [1,4,7]、[1,4,8]、[1,5,7]、[1,5,8]、[1,5,9]、[2,4,7]、[2,4,8]、[2,5,7]、[2,5,8]、[2,5,9]、[2,6,9]、[3,5,7]、[3,5,8]、[3,5,9]、[3,6,8]、[3,6,9]，最小的路徑和是 [1,4,7]，和為 12。
為了解決這個問題，我們將遵循以下步驟：
- n := 陣列的大小
- for i in range n – 2 down to 0
- for j in range 0 to n
- 如果 j – 1 < 0，則 x1 := inf，否則 x1 := matrix[i + 1, j - 1]
- x2 := matrix[i + 1, j]
- 如果 j + 1 >= n，則 x3 := inf，否則 x3 := matrix[i + 1, j + 1]
- matrix[i, j] := matrix[i, j] + min of x1, x2, x3
- for j in range 0 to n
- ans := inf
- for i in range 0 to n – 1
- ans := min of ans and matrix[0, i]
- return ans
讓我們看看下面的實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& a) {
int n = a.size();
for(int i =n-2;i>=0;i--){
for(int j =0;j<n;j++){
int x1 = j-1<0?INT_MAX:a[i+1][j-1];
int x2 = a[i+1][j];
int x3 = j+1>=n?INT_MAX:a[i+1][j+1];
a[i][j]+= min({x1,x2,x3});
}
}
int ans = INT_MAX;
for(int i =0;i<n;i++){
ans = min(ans,a[0][i]);
}
return ans;
}
};
main(){
vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
Solution ob;
cout <<(ob.minFallingPathSum(v));
}輸入
[[1,2,3],[4,5,6],[7,8,9]]
輸出
12
更新於: 2020年4月30日
203 次瀏覽
廣告