資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++矩陣中從上到下的最大路徑和
問題陳述
考慮一個n*n矩陣。假設矩陣中的每個單元格都分配了一個值。我們只能從第i行的每個單元格移動到第i+1行中對角線上的更高單元格[即，只能從單元格(i, j)移動到單元格(i+1, j-1)和單元格(i+1, j+1)]。找到從頂行到底行遵循上述條件的路徑，使得獲得最大和。
示例
If given input is:
{
{5, 6, 1, 17},
{-2, 10, 8, -1},
{ 3, -7, -9, 4},
{12, -4, 2, 2}
}最大和為 (17 + 8 + 4 + 2) = 31
演算法
這個想法是找到最大和，或者所有從第一行每個單元格開始的路徑，最後返回第一行中所有值的最大值。
我們使用動態規劃，因為許多子問題的結果會被反覆需要。
示例
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int getMaxMatrixSum(int mat[SIZE][SIZE], int n){
if (n == 1) {
return mat[0][0];
}
int dp[n][n];
int maxSum = INT_MIN, max;
for (int j = 0; j < n; j++) {
dp[n - 1][j] = mat[n - 1][j];
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
max = INT_MIN;
if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) {
max = dp[i + 1][j - 1];
}
if (((j + 1) < n) && (max < dp[i + 1][j + 1])) {
max = dp[i + 1][j + 1];
}
dp[i][j] = mat[i][j] + max;
}
}
for (int j = 0; j < n; j++) {
if (maxSum < dp[0][j]) {
maxSum = dp[0][j];
}
}
return maxSum;
}
int main(){
int mat[SIZE][SIZE] = {
{5, 6, 1, 17},
{-2, 10, 8, -1},
{3, -7, -9, 4},
{12, -4, 2, 2}
};
int n = 4;
cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
return 0;
}輸出
編譯並執行上述程式時，將生成以下輸出：
Maximum Sum = 31
更新於：2020年1月30日
207 次瀏覽
廣告