Skip to content

DP Grid Advanced

Table of Contents

1594. Maximum Non Negative Product in a Matrix

1301. Number of Paths with Max Score

2435. Paths in Matrix Whose Sum Is Divisible by K

174. Dungeon Game

329. Longest Increasing Path in a Matrix

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, dynamic programming, depth first search, breadth first search, graph, topological sort, memoization, matrix

329. Longest Increasing Path in a Matrix - Python Solution
from typing import List


# DP - 2D
def longestIncreasingPath(matrix: List[List[int]]) -> int:
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def dfs(r, c):
        if dp[r][c]:
            return dp[r][c]
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                dp[r][c] = max(dp[r][c], dfs(nr, nc))
        dp[r][c] += 1
        return dp[r][c]

    res = float("-inf")
    for i in range(m):
        for j in range(n):
            res = max(res, dfs(i, j))

    return res


matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
print(longestIncreasingPath(matrix))  # 4

2328. Number of Increasing Paths in a Grid

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, dynamic programming, depth first search, breadth first search, graph, topological sort, memoization, matrix

2267. Check if There Is a Valid Parentheses String Path

1937. Maximum Number of Points with Cost

3363. Find the Maximum Number of Fruits Collected

1463. Cherry Pickup II

741. Cherry Pickup

3459. Length of Longest V-Shaped Diagonal Segment

2510. Check if There is a Path With Equal Number of 0's And 1's

Comments