DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 68: Python Unique Paths in Grid - O(m*n) DP Solution for Robot Paths (LeetCode #62 Vibes)

#challenge #python #algorithms #programming

Welcome to Day 68 of the #80DaysOfChallenges journey! This intermediate challenge solves the classic unique paths in a grid problem (LeetCode #62), counting ways to reach bottom-right from top-left with only right/down moves, using dynamic programming to fill a 2D table in O(m*n) time. It builds the DP grid with base cases on first row/column, then sums paths from above/left, a foundational DP pattern for grid traversal and path counting. If you're advancing from basic DP to grid problems or prepping for interviews with robot paths/mazes, this "Python unique paths" script demonstrates a function that's optimal, space-efficient, and easy to extend for obstacles or costs.

💡 Key Takeaways from Day 68: Unique Paths Function

This task features a function that initializes a DP table with 1s on edges (only one way), then fills inward by summing incoming paths. It's a bottom-up DP pattern: base edges, build up. We'll detail: function with DP table setup, loops for filling grid, and main with input and print.

1. Function Design: Validate and Init DP Table

The unique_paths function takes m rows, n cols, returns count:

def unique_paths(m: int, n: int) -> int:
    """Return number of unique paths from top-left to bottom-right."""
    dp = [[0] * n for _ in range(m)]   # create DP table
Enter fullscreen mode Exit fullscreen mode

Creates m x n grid of 0s. Could optimize to 1D row for O(n) space, but 2D clearer.

2. Base Cases: Fill First Row and Column

Set edges to 1 (one way: all right or down):

    # first row: only one way (move right)
    for j in range(n):
        dp[0][j] = 1

    # first column: only one way (move down)
    for i in range(m):
        dp[i][0] = 1
Enter fullscreen mode Exit fullscreen mode

This seeds the DP, as no choices on edges.

3. Fill Grid: Sum From Above and Left

Core nested loops:

    # fill the rest of the grid
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]  # from top + left

    return dp[m - 1][n - 1]   # bottom-right corner
Enter fullscreen mode Exit fullscreen mode

Each cell sums ways from above (down move) and left (right move). For 3x3: bottom-right = 6. O(m*n) time/space.

4. Main Interactive: Rows/Cols Input

Script prompts m/n, computes:

rows = int(input("Enter number of rows (m): ").strip())
cols = int(input("Enter number of columns (n): ").strip())

result = unique_paths(rows, cols)
print(f"Unique paths in a {rows}x{cols} grid: {result}")
Enter fullscreen mode Exit fullscreen mode

Simple, assumes positive ints (add validation for prod).

🎯 Summary and Reflections

This unique paths DP fills grid by summing incoming, classic for counting. It reinforced:

  • Base edges: Seed with 1s for single paths.
  • Sum pattern: Each cell = above + left.
  • Grid DP basics: Extendable to obstacles (set 0).

Reflections: Math combo C(m+n-2, m-1), but DP flexible for variants. Space optimize to last row.

Advanced Alternatives: 1D DP row. Memo recursion (top-down). Binomial coeff for pure math. Your path count? Share!

🚀 Next Steps and Resources

Day 68 counted grid paths. In #80DaysOfChallenges? Added obstacles? Post!

Top comments (0)