DP on LeetCode: 3 problems with recurrence formulas

Dynamic Programming: An Intuitive Approach to Three LeetCode Problems

Dynamic programming (DP) solves counting and optimization problems through recurrence relations. Let's examine problems 62 (Unique Paths), 64 (Minimum Path Sum), and 70 (Climbing Stairs). Each demonstrates key DP characteristics: optimal substructure and overlapping subproblems.

Unique Paths: Counting Routes on a Grid

A robot moves on an m × n grid from (0,0) to (m-1,n-1), moving only right or down. Find the number of unique paths.

Any path consists of (m-1) down steps and (n-1) right steps. A combinatorial solution uses the binomial coefficient C(m+n-2, m-1). However, an algorithmic approach is expected in interviews.

Define dp[i][j] as the number of paths to cell (i,j). Recurrence relation:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Boundary conditions:

• dp[0][j] = 1 (first row)
• dp[i][0] = 1 (first column)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

Time complexity O(m·n). The solution uses the addition rule for disjoint sets of paths.

Minimum Path Sum: Minimizing Path Cost

Given an m × n grid with non-negative numbers. Find the minimum sum of values on a path from (0,0) to (m-1,n-1) when moving right or down.

A greedy algorithm (choosing the local minimum) fails—it leads to dead ends with high values. Global optimization is required.

Define dp[i][j] as the minimum cost to reach (i,j). Recurrence relation:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Boundary conditions:

dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = grid[0][j] + dp[0][j-1]
for i in range(1, m): dp[i][0] = grid[i][0] + dp[i-1][0]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

Complexity O(m·n). Each value is used for all subsequent cells.

Climbing Stairs: Fibonacci Numbers in DP

Climbing stairs with n steps (1 ≤ n ≤ 45), each step is 1 or 2 stairs. Find the number of ways.

For n=1: 1 way

n=2: 2 ways (1+1, 2)

n=3: 3 ways (1+1+1, 1+2, 2+1)

Recurrence relation:

dp[n] = dp[n-1] + dp[n-2]

Simple recursion leads to exponential complexity O(φ^n) due to repeated computations. A DP array solves the problem:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

An optimized version uses O(1) memory with two variables.

Signs of Dynamic Programming Problems

Apply DP when two conditions are met:

• Optimal substructure: the optimal solution consists of optimal solutions to subproblems.
• Overlapping subproblems: the same subproblems are computed multiple times.

| Problem | Optimal Substructure | Overlapping Subproblems |

|--------|-------------------------|---------------------------|

| Unique Paths | Sum of paths from adjacent cells | Each path to a cell overlaps |

| Min Path Sum | Min cost from neighbors | Cost is used for all cells below/right |

| Climbing Stairs | Sum from n-1 and n-2 | Recursive calls repeat |

Key Takeaways

• Recurrence relations define the essence of DP: dp[i][j] depends only on adjacent already computed values.
• Boundary conditions are filled separately for the first row/column or base cases.
• Time complexity is always O(input size) with proper tabular implementation.
• Memory can be optimized: for grids—one row, for linear problems—two variables.
• Combinatorics often provides a mathematical shortcut, but algorithmic solutions are more important for interviews.

— Editorial Team