Counting Unique Paths in a 2D Grid Matrix
Consider a scenario where an automated agent is situated at the top-left corner of a grid defined by m rows and n columns. The agent is strictly limited to movements either towards the right or downwards. The task is to calculate the total number of distinct routes the agent can take to arrive at the bottom-right corner of the grid.
To solve this efficiently, a dynamic programming approach is utilized. We can observe that to reach any specific cell (i, j), the agent must arrive from either the cell directly above it (i-1, j) or the cell immediately to the left (i, j-1). Consequently, the total number of paths to (i, j) is the sum of the paths to those two preceding cells.
We can optimize space complexity by using a single-dimensional array. Initially, the array is populated with 1s because there is exactly one way to reach any cell in the first row (moving consistently right) or first column (moving consistently down).
def calculate_unique_paths(rows, cols):
# Initialize a 1D array to store path counts for the current row
# Initially, all values are 1 because the first row has only one path
path_counts = [1] * cols
# Iterate through the grid starting from the second row
for r in range(1, rows):
for c in range(1, cols):
# The number of paths to the current cell is the sum of
# the paths from the cell above (path_counts[c]) and
# the cell to the left (path_counts[c-1])
path_counts[c] += path_counts[c - 1]
return path_counts[-1]