資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究N x N 網格中的最小下降路徑總和，用 C++ 編寫
問題陳述
- 給定一個 N x N 的整數矩陣 A。任務是找到下降穿過 A 的最小路徑總和。
- 下降路徑將從第一行的某個元素開始，在最後一行結束。
- 它從每一行選擇一個元素。下一行的選擇必須在與上一行相差至多 1 的列中
示例
If N = 2 and matrix is:
{
{5, 10},
{25, 15}
} then output will be 20 as element 5 and 15 are selected示例
#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
for (int row = MAX - 2; row >= 0; --row) {
for (int col = 0; col < MAX; ++col) {
int val = matrix[row + 1][col];
if (col > 0) {
val = min(val, matrix[row +1][col - 1]);
}
if (col + 1 < MAX) {
val = min(val, matrix[row +1][col + 1]);
}
matrix[row][col] = matrix[row][col] +val;
}
}
int result = INT_MAX;
for (int i = 0; i < MAX; ++i)
result = min(result, matrix[0][i]);
return result;
}
int main() {
int matrix[MAX][MAX] = {
{5, 10},
{25, 15},
};
cout << "Minimum sum path = " << getMinSumPath(matrix)
<< endl;
return 0;
}編譯並執行以上程式後，將生成如下輸出
輸出
Minimum sum path = 20
更新於: 2019-12-23
143 次瀏覽
廣告