Đường dẫn dài nhất trong 2-D chứa trình tự ngày càng tăng trong JavaScript

Tăng trình tự

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

Ví dụ,

4, 6, 8, 9, 11, 14 is increasing sequence
3, 3, 3, 3, 3, 3, 3 is also an increasing sequence

Vấn đề:

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng số 2-D, arr, làm đối số duy nhất. Hàm của chúng ta sẽ tìm và trả về độ dài của đường dẫn dài nhất đó trong mảng chỉ chứa các số tăng dần.

Ví dụ:nếu đầu vào của hàm là -

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

Sau đó, đầu ra phải là -

const output = 4;

Giải thích đầu ra:

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

Ví dụ

Mã cho điều này sẽ là -

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

• Ở đây, chúng tôi đã sử dụng tìm kiếm đầu tiên theo độ sâu backtracking.

• Hàm đệ quy chỉ trả về đường dẫn tăng dài nhất cho một hàng và cột nhất định

• Nếu chúng tôi đã có bản ghi về đường đi tăng dài nhất cho một vị trí, thì chúng tôi có thể chỉ cần trả lại con đường đó.

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

4