Đề bài
Cho ma trận n*n, mỗi ô có giá trị. Từ ô (i, j) chỉ được đi đến (i+1, j-1) hoặc (i+1, j+1) (chéo dưới trái/phải). Tìm đường đi từ hàng đầu đến hàng cuối cho tổng lớn nhất.
Ví dụ
Input: { {5, 6, 1, 17}, {-2, 10, 8, -1}, { 3, -7, -9, 4}, {12, -4, 2, 2} }Tổng lớn nhất = 31 (17 + 8 + 4 + 2)
Thuật toán
- Tìm tổng lớn nhất của tất cả đường đi bắt đầu từ mỗi ô hàng đầu, trả về max của hàng đầu.
- Dùng quy hoạch động vì nhiều bài toán con lặp lại.
Ví dụ
#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 << "Tổng lớn nhất = " << getMaxMatrixSum(mat, n) << endl; return 0; }Kết quả
Tổng lớn nhất = 31