DP intro

26 Mar 2025

Introduction to Dynamic Programming

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is particularly useful when a problem has overlapping subproblems and optimal substructure, meaning the optimal solution to the problem can be constructed from optimal solutions to its subproblems.

The main idea behind DP is to solve each subproblem once and store its result, avoiding the need for redundant computations. This approach is typically implemented using either:

Top-Down Approach (Memoization): Recursively solving subproblems and storing their results.
Bottom-Up Approach (Tabulation): Iteratively solving subproblems starting from the simplest cases and combining them to solve larger subproblems.

DP is widely used in various domains such as operations research, bioinformatics, and economics, addressing problems like sequence alignment, resource allocation, and decision-making processes.

Selected LeetCode Hard Problem: Longest Increasing Path in a Matrix

One exemplary problem that utilizes dynamic programming is the Longest Increasing Path in a Matrix.

Problem Description

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

From each cell, you can 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).

Example

Input:

matrix = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Output: 4

Explanation: The longest increasing path is [1, 2, 6, 9].

Hints and Key Observations

Graph Representation: Think of the matrix as a directed graph where each cell is a node, and there is a directed edge from one node to another if you can move from the first to the second and the value in the second is greater than in the first.
Topological Ordering: The problem can be approached by processing nodes in topological order, ensuring that when processing a node, all nodes leading into it have been processed.
Memoization: Since there are overlapping subproblems (the longest path from a cell depends on the longest paths from its neighbors), use memoization to store the results of subproblems.

Plan of Attack

Initialize a Memoization Table: Create a 2D array memo where memo[i][j] will store the length of the longest increasing path starting from cell (i, j).
Depth-First Search (DFS): Define a recursive function that computes the longest increasing path starting from a given cell using DFS.
Iterate Through Each Cell: For each cell in the matrix, use the DFS function to compute the longest increasing path starting from that cell, utilizing the memoization table to avoid redundant calculations.
Keep Track of the Maximum Path Length: Update the maximum path length encountered during the iterations.

Detailed Solution with Inline Comments

def longestIncreasingPath(matrix):
    if not matrix or not matrix[0]:
        return 0

    # Dimensions of the matrix
    m, n = len(matrix), len(matrix[0])
    # Memoization table to store results of subproblems
    memo = [[-1] * n for _ in range(m)]

    # Directions for moving: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def dfs(i, j):
        # If the result is already computed, return it
        if memo[i][j] != -1:
            return memo[i][j]

        # Initialize the maximum length to 1 (the cell itself)
        max_length = 1

        # Explore all four directions
        for di, dj in directions:
            ni, nj = i + di, j + dj
            # Check if the new position is within bounds and is an increasing step
            if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                # Recursively find the length from the neighboring cell
                length = 1 + dfs(ni, nj)
                # Update the maximum length
                max_length = max(max_length, length)

        # Store the result in the memoization table
        memo[i][j] = max_length
        return max_length

    # Initialize the result
    result = 0
    # Compute the longest increasing path starting from each cell
    for i in range(m):
        for j in range(n):
            result = max(result, dfs(i, j))

    return result

Explanation

Initialization: We first check if the matrix is empty. Then, we initialize the dimensions m and n, and create a memoization table memo initialized to -1, indicating uncomputed states.
DFS Function: The dfs function computes the longest increasing path starting from cell (i, j). It first checks if the result is already computed. If not, it initializes max_length to 1 (considering the cell itself) and explores all four possible directions. For each valid move to a cell with a greater value, it recursively computes the path length and updates max_length. The computed result is then stored in memo[i][j].
Iterate Through Each Cell: We iterate through each cell in the matrix, invoking the dfs function to ensure all paths are considered, and update the overall maximum path length.

URL to the Problem

Longest Increasing Path in a Matrix

This problem effectively demonstrates the power of dynamic programming in solving complex problems by breaking them down into manageable subproblems and utilizing memoization to optimize performance.

Numeric Jungle