Cho ma trận vuông n x n các phần tử riêng biệt. Tìm độ dài đường đi dài nhất sao cho các ô trên đường đi tăng dần 1 đơn vị, di chuyển 4 hướng. Ví dụ ma trận 3x3 → đường đi dài nhất 4 (6→7→8→9).
Dùng quy hoạch động với bảng nhớ dp[][], đệ quy tính độ dài đường đi bắt đầu từ mỗi ô.
Ví dụ
#include <iostream> #define n 3 using namespace std; int getLongestPathLengthUtil(int i, int j, int matrix[n][n], int table[n][n]) { if (i < 0 || i >= n || j < 0 || j >= n) return 0; if (table[i][j] != -1) return table[i][j]; int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN; if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1])) x = 1 + getLongestPathLengthUtil(i, j + 1, matrix, table); if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1])) y = 1 + getLongestPathLengthUtil(i, j - 1, matrix, table); if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j])) z = 1 + getLongestPathLengthUtil(i - 1, j, matrix, table); if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j])) w = 1 + getLongestPathLengthUtil(i + 1, j, matrix, table); return table[i][j] = max(x, max(y, max(z, max(w, 1)))); } int getLongestPathLength(int matrix[n][n]) { int result = 1; int table[n][n]; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) table[i][j] = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (table[i][j] == -1) getLongestPathLengthUtil(i, j, matrix, table); result = max(result, table[i][j]); } } return result; } int main() { int mat[n][n] = { { 1, 2, 9 }, { 5, 3, 8 }, { 4, 6, 7 } }; cout << "Length of the longest path is "<< getLongestPathLength(mat); }
Kết quả
Length of the longest path is 4