Đường đi dài nhất trong mảng 2D chứa dãy tăng dần trong JavaScript

Dãy tăng dần

Một dãy số mà mỗi phần tử tiếp theo lớn hơn hoặc bằng phần tử trước đó gọi là dãy tăng dần.

Ví dụ:

4, 6, 8, 9, 11, 14 là dãy tăng dần
3, 3, 3, 3, 3, 3, 3 cũng là dãy tăng dần

Mô tả vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào mảng 2D số arr làm đối số duy nhất. Hàm phải tìm và trả về độ dài đường đi dài nhất trong mảng chỉ chứa các số tăng dần.

Ví dụ, nếu đầu vào là:

const arr = [ 
  [4, 5, 6], 
  [4, 3, 7], 
  [3, 3, 2] 
];

Thì đầu ra nên là:

const output = 4;

Giải thích đầu ra

Vì dãy tăng dài nhất là 4, 5, 6, 7.

Ví dụ minh họa

Mã thực hiện (DFS + memoization):

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));

Giải thích mã

Ý tưởng:

• Sử dụng tìm kiếm sâu (DFS) có quay lui (backtracking).
• Hàm đệ quy trả về đường đi tăng dài nhất từ một hàng, cột cho trước.
• Nếu đã có kết quả lưu cho vị trí đó, trả về ngay (memoization).

Đầu ra

Kết quả trong console sẽ là:

4