Teaching Kids Programming – Count Out of Boundary Path via Top Down Dynamic Programming Algorithm (Recursion with Memoization)

Teaching Kids Programming: Videos on Data Structures and Algorithms

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.

Compute Out of Boundary Paths

Example 1:
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6

Example 2:
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output: 12

Constraints:
1 <= m, n <= 50
0 <= maxMove <= 50
0 <= startRow < m
0 <= startColumn < n

Hint 1
Is traversing every path feasible? There are many possible paths for a small matrix. Try to optimize it.
Hint 2
Can we use some space to store the number of paths and update them after every move?
Hint 3
One obvious thing: the ball will go out of the boundary only by crossing it. Also, there is only one possible way the ball can go out of the boundary from the boundary cell except for corner cells. From the corner cell, the ball can go out in two different ways. Can you use this thing to solve the problem?

Count Out of Boundary Path via Top Down Dynamic Programming Algorithm (Recursion with Memoization)

We can simulate the process, at each cell, we have four directions to walk, which leads to four different paths. When we are outside the boundary, we have found one out-of-boundary path, then we have to stop. When we have reached the maxMove moves, and we are still in the grid, we need to stop and do nothing.

We can use Recursion to simulate the process. That is brute force. However, it is slow as we repeat our calculations for the intermediate nodes. We can fix this by caching the results aka memoization, also known as the Top Down Dynamic Programming Algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def findPaths(self, rows: int, cols: int, maxMove: int, startRow: int, startColumn: int) -> int:
 
        @cache
        def f(m, r, c):
            if r == rows or r < 0 or c == cols or c < 0:
                return 1
            if m == 0:
                return 0
            ans = f(m - 1, r - 1, c) + \
                f(m - 1, r + 1, c) + \
                f(m - 1, r, c - 1) + \
                f(m - 1, r, c + 1)
            return ans
 
        return f(maxMove, startRow, startColumn) % 1000000007

class Solution:
    def findPaths(self, rows: int, cols: int, maxMove: int, startRow: int, startColumn: int) -> int:

        @cache
        def f(m, r, c):
            if r == rows or r < 0 or c == cols or c < 0:
                return 1
            if m == 0:
                return 0
            ans = f(m - 1, r - 1, c) + \
                f(m - 1, r + 1, c) + \
                f(m - 1, r, c - 1) + \
                f(m - 1, r, c + 1)
            return ans

        return f(maxMove, startRow, startColumn) % 1000000007

–EOF (The Ultimate Computing & Technology Blog) —