Increasing Sequence
ลำดับที่แต่ละ element >= element ก่อนหน้า
ปัญหา
หาความยาว longest increasing path ใน 2D matrix (เคลื่อนที่ 4 ทิศทาง)
ตัวอย่าง
matrix = [[4,5,6],[4,3,7],[3,3,2]] longest path: 4->5->6->7 length = 4
ตัวอย่างโค้ด
const arr = [
[4, 5, 6],
[4, 3, 7],
[3, 3, 2]
];
const longestIncreasingPath = (arr = []) => {
let longest = 0;
let dp = Array(arr.length).fill(null).map(() =>
Array(arr[0].length).fill(1)
);
const backtracking = (row, col) => {
if (dp[row][col] != 1) return dp[row][col];
let dRow = [1, 0, -1, 0];
let dCol = [0, 1, 0, -1];
for (let i = 0; i < dRow.length; i++) {
let nR = row + dRow[i], nC = col + dCol[i];
if (nR >= 0 && nR < arr.length && nC >= 0 && nC < arr[0].length && arr[nR][nC] > arr[row][col]) {
dp[row][col] = Math.max(dp[row][col], 1 + backtracking(nR, nC));
}
}
return dp[row][col];
};
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[0].length; j++) {
longest = Math.max(longest, backtracking(i, j));
}
}
return longest;
};
console.log(longestIncreasingPath(arr));
ผลลัพธ์
4
คำอธิบาย
DFS + Memoization (DP): dp[row][col] = longest path เริ่มจาก (row,col)
คำนวณแบบ top-down: หากคำนวณแล้วคืนค่าทันที มิฉะนั้น recursive 4 ทิศทางหา neighbor ที่มากกว่า
Time: O(m*n) ทุก cell คำนวณได้สูงสุด 1 ครั้ง, Space: O(m*n)
