[JS] Longest Increasing Path in a Matrix

🔒 문제 (LeetCode 329)

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

 

🌊 입출력

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

 

---

 

🔑 해결

🌌 알고리즘 - DFS & DP(memoization)

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function(matrix) {
    const [m ,n] = [matrix.length, matrix[0].length]
    const dir = [[0, 1], [-1, 0], [0, -1], [1, 0]] 
    const dp = new Array(m).fill().map(() => new Array(n).fill(0))
    let answer = 0
    
    const dfs = (r, c) => {        
        if(dp[r][c]) return dp[r][c]  
        
        dir.forEach(([x, y]) => {
            const [nr, nc] = [r + x, c + y]
            if(nr >= 0 && nc >= 0 && nr < m && nc < n && matrix[nr][nc] > matrix[r][c]) {
                dp[r][c] = Math.max(dp[r][c], 1 + dfs(nr, nc))
            }
        })
        
        if(!dp[r][c]) dp[r][c] = 1
        answer = Math.max(answer, dp[r][c])
        
        return dp[r][c]
    }
    
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(!dp[i][j]) dfs(i, j)
        }
    }
    
    return answer
};