剑指 Offer II 112. 最长递增路径

记忆化dfs

class Solution {
    let dx = [0,0,1,-1]
    let dy = [1,-1,0,0]
 func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
        let row = matrix.count
        let col = matrix.first!.count
        var maxLen = 0
        let temp = Array.init(repeating: 1, count: col)
        var dp = Array.init(repeating: temp, count: row)
  
        for i in 0..<row{
            for j in 0..<col {
                maxLen = max(maxLen, dfs(i,j,row,col,matrix,&dp))
            }
        }
    
        return maxLen
    }
    
    func dfs(_ i:Int, _ j:Int, _ row:Int, _ col:Int,_ matrix:[[Int]],_ dp:inout [[Int]]) ->Int{
     
        if dp[i][j] != 1 {
            return dp[i][j]
        }

        for m in 0..<4 {
            let tempRow = i + dx[m] , tempCol = j + dy[m]
            if tempRow >= 0 && tempRow < row && tempCol >= 0 && tempCol < col && matrix[tempRow][tempCol] > matrix[i][j]{
                dp[i][j] = max(dp[i][j], dfs(tempRow,tempCol,row,col,matrix,&dp) + 1)
            }
        }
        
        
        return dp[i][j]
            
       
    }
}