Path Sum: Four Ways

NOTE: This problem is a significantly more challenging version of Problem 81.
In the $5$ by $5$ matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to $2297$.

$$
\begin{pmatrix}
\color{red}{131} & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\
\color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & \color{red}{150}\\
630 & 803 & 746 & \color{red}{422} & \color{red}{111}\\
537 & 699 & 497 & \color{red}{121} & 956\\
805 & 732 & 524 & \color{red}{37} & \color{red}{331}
\end{pmatrix}
$$

Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing an $80$ by $80$ matrix.

To solve this problem, we need to find the minimal path sum from the top left to the bottom right in a given matrix, just like in the example provided. We can use a dynamic programming approach to solve this problem efficiently.

Here is a step-by-step solution using Python programming:

1. Read the matrix from the provided text file. We’ll assume the file is named “matrix.txt”. The matrix will be stored as a 2D list.

“`python
def read_matrix(file_name):
matrix = []
with open(file_name, ‘r’) as file:
for line in file:
row = list(map(int, line.strip().split(‘,’))) # assuming each element is separated by a comma
matrix.append(row)
return matrix

matrix = read_matrix(“matrix.txt”)
“`

2. Initialize a new 2D list, `dp`, with the same dimensions as the matrix. `dp[i][j]` will represent the minimal path sum to reach the cell at position `(i,j)` from the top left corner.

“`python
dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
dp[0][0] = matrix[0][0] # the top-left cell has the same minimal path sum as its value
“`

3. Calculate the minimal path sum for each cell in the matrix.

“`python
# Calculate minimal path sum for the first row (moving only right)
for j in range(1, len(matrix[0])):
dp[0][j] = dp[0][j-1] + matrix[0][j]

# Calculate minimal path sum for the first column (moving only down)
for i in range(1, len(matrix)):
dp[i][0] = dp[i-1][0] + matrix[i][0]

# Calculate minimal path sum for the remaining cells
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
# Choose the minimum path sum from either coming from the left or from above
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + matrix[i][j]
“`

4. The minimal path sum from the top left to the bottom right will be stored in `dp[-1][-1]`.

“`python
minimal_path_sum = dp[-1][-1]
print(“The minimal path sum is:”, minimal_path_sum)
“`

Putting it all together, here is the complete Python code to solve the problem:

“`python
def read_matrix(file_name):
matrix = []
with open(file_name, ‘r’) as file:
for line in file:
row = list(map(int, line.strip().split(‘,’))) # assuming each element is separated by a comma
matrix.append(row)
return matrix

matrix = read_matrix(“matrix.txt”)

dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
dp[0][0] = matrix[0][0]

for j in range(1, len(matrix[0])):
dp[0][j] = dp[0][j-1] + matrix[0][j]

for i in range(1, len(matrix)):
dp[i][0] = dp[i-1][0] + matrix[i][0]

for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + matrix[i][j]

minimal_path_sum = dp[-1][-1]
print(“The minimal path sum is:”, minimal_path_sum)
“`

By running this code, you will get the minimal path sum from the top left to the bottom right of the provided matrix.

More Answers: