Travel & Candies — Grid Path DP

Grid path DP models a traveler moving from the top-left to the bottom-right of a matrix, taking only right or down steps. Cells hold costs, candies, or obstacles. This lesson covers unique paths (LeetCode 62), minimum path sum (64), maximum candies, and obstacles (63) — with full C, Java, and Python code and trace tables.

Overview

A robot (or traveler) starts at (0, 0) and must reach (m−1, n−1). From each cell it may move right or down only. The grid value at each cell contributes to the answer depending on the problem:

• Count paths — how many distinct routes exist?
• Minimum cost — smallest sum of cell values along any path
• Maximum candies — largest sum of rewards collected along any path

Sample grid (candies / costs):
       col0  col1  col2
row0    1     3     1
row1    1     5     1
row2    4     2     1

Start S at (0,0)  →  Goal G at (2,2)
Allowed moves:  → right   or   ↓ down

Min-cost path:  1 → 3 → 1 → 1 → 1  = 7
Max-candy path: 1 → 3 → 5 → 2 → 1  = 12

Unique Paths — Count Routes

Problem: An m × n grid with no obstacles — how many distinct paths from top-left to bottom-right?

State: dp[i][j] = number of paths to reach cell (i, j).

Recurrence: dp[i][j] = dp[i−1][j] + dp[i][j−1] (only one direction if on top or left edge).

Base: First row and first column are all 1 (only one way along each edge).

Minimum Path Sum — Min-Cost Travel

Problem (LeetCode 64): Each cell has a non-negative cost. Find the path from (0,0) to bottom-right with the minimum total cost.

Recurrence: dp[i][j] = min(dp[i−1][j], dp[i][j−1]) + grid[i][j]

Base: Fill first row and first column as cumulative sums from the start.

Minimum Path Sum Code (C, Java, Python)

Python

def min_path_sum(grid):
    """LeetCode 64 — minimum cost path top-left to bottom-right."""
    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] = dp[0][j - 1] + grid[0][j]   # first row: only from left
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]   # first col: only from top

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

    return dp[m - 1][n - 1]


if __name__ == "__main__":
    grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
    print(f"min path sum = {min_path_sum(grid)}")  # 7

Java

public class MinPathSum {

    /** Minimum path sum — bottom-up 2D DP. */
    public static int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
        for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(minPathSum(grid)); // 7
    }
}

C

#include <stdio.h>

#define MAX 100

int min2(int a, int b) { return a < b ? a : b; }

/* Minimum path sum on m x n grid */
int min_path_sum(int grid[MAX][MAX], int m, int n) {
    int dp[MAX][MAX];
    int i, j;

    dp[0][0] = grid[0][0];
    for (j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            dp[i][j] = min2(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[m - 1][n - 1];
}

int main(void) {
    int grid[MAX][MAX] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    printf("%d\n", min_path_sum(grid, 3, 3)); /* 7 */
    return 0;
}

Minimum Path Sum Output & Trace

Program output (all three languages)

DP table trace — minimum path sum

Maximum Candies — Best Reward Path

Problem: Each cell holds candies (non-negative). Collect all candies on the chosen path. Maximize the total from start to goal.

Recurrence: Same grid skeleton — replace min with max:

dp[i][j] = max(dp[i−1][j], dp[i][j−1]) + grid[i][j]

Maximum Candies Code (C, Java, Python)

Python

def max_candies(grid):
    """Maximum candies collected on a right/down path."""
    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] = dp[0][j - 1] + grid[0][j]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]

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

    return dp[m - 1][n - 1]


if __name__ == "__main__":
    grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
    print(f"max candies = {max_candies(grid)}")  # 12

Java

public class MaxCandies {

    public static int maxCandies(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
        for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(maxCandies(grid)); // 12
    }
}

C

#include <stdio.h>

#define MAX 100

int max2(int a, int b) { return a > b ? a : b; }

int max_candies(int grid[MAX][MAX], int m, int n) {
    int dp[MAX][MAX];
    int i, j;

    dp[0][0] = grid[0][0];
    for (j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            dp[i][j] = max2(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[m - 1][n - 1];
}

int main(void) {
    int grid[MAX][MAX] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    printf("%d\n", max_candies(grid, 3, 3)); /* 12 */
    return 0;
}

Maximum Candies Output & Trace

Program output

DP table trace — maximum candies (final dp values)

Obstacles & Blocked Cells

Unique Paths II (LeetCode 63): Cells marked as obstacles (1) cannot be entered. If start or goal is blocked, return 0.

Modification: When grid[i][j] == 1, set dp[i][j] = 0. Otherwise use the usual sum (count), min, or max recurrence.

See also unique paths in grid (sidebar topic) for extended grid variants including cherry pickup and dungeon game.

Space Optimization

Because each cell depends only on the cell above and to the left, the full m × n table can be reduced to a single row (or two rows):

2D:  dp[i][j] = f(dp[i-1][j], dp[i][j-1]) + grid[i][j]
1D:  dp[j] = f(dp[j], dp[j-1]) + grid[i][j]   // update left→right per row

Space: O(m×n) → O(n)   Time stays O(m×n)

More Examples

Example 1: Unique paths 3×3 (no obstacles)

Example 2: Single row grid

Example 3: Complexity summary

Approach Comparison

Real-Life Applications

Grid path DP models any journey on a map with fixed move rules and per-cell costs or rewards.

Interview Tips

1. Confirm moves: only right/down? or four directions? (four directions → BFS or different DP)
2. Clarify: count paths, min cost, or max reward?
3. Draw a small 3×3 grid and fill the DP table before coding.
4. Initialize first row and first column explicitly — common bug source.
5. For obstacles: if grid[i][j] is blocked, set dp[i][j]=0 (count) or skip.
6. Mention O(n) space optimization with a 1D array after the 2D solution.
7. Unique paths without obstacles: offer combinatorial formula C(m+n−2, m−1).
8. Connect min path to 1D DP (single row) and to extended grid topics.