#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/multi-dimensional-dp/grid-1-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/multi-dimensional-dp/grid-1-implementation

Repovive

Grid 1 - Implementation - Multi-Dimensional DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units

Open in Course

Grid 1 - Implementation

The code

Here is the implementation for Grid 1 (AtCoder DP- $H$ ):

MOD := 1000000007
Input: H, W, grid[1..H][1..W]

dp := 2D array of size H × W, all set to 0

if grid[1][1] = '.' then
    dp[1][1] := 1

for i from 1 to H
    for j from 1 to W
        if grid[i][j] = '#' then
            dp[i][j] := 0
        else
            if i > 1 then
                dp[i][j] := (dp[i][j] + dp[i - 1][j]) mod MOD
            if j > 1 then
                dp[i][j] := (dp[i][j] + dp[i][j - 1]) mod MOD

return dp[H][W]

You fill the grid row by row, left to right. For each empty cell, add the paths from above and from the left. Wall cells stay at $0$ , blocking all paths through them. The mod keeps numbers from overflowing. Trace a small $3 \times 3$ grid with one wall to see how blocked cells cut off entire regions.

Time complexity: $O(H \cdot W)$ .

Space complexity: $O(H \cdot W)$ , reducible to $O(W)$ by keeping only the current and previous rows.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!