Given a right-angled triangle-shaped matrix, find the shortest path sum from the top element to any element in the last row of the matrix.
We can only move down from the present cell at any given time. Hence, the legal movements from cell (x,y) are either (x+1,y) or (x+1,y+1). For example,
Input: mat = [
[4],
[1, 3],
[1, 2, 1],
[8, 4, 5, 1]
]
Output: 9
Explanation: The minimum path is [4, 3, 1, 1] having sum 9.
A closer look reveals that this problem may be recursively divided into smaller subproblems, with each problem being repeated numerous times. Dynamic programming can be used to solve problems with optimal substructure and overlapping subproblems.
The idea is to save subproblem solutions rather than repeatedly computing them. We begin by building a 2D array T[][] to record the solutions to the subproblems, where T[i][j] will hold the minimum sum path for the ith row and jth column. Here, T[i][j] would equal the total of the current cell and the lower of its bottom and bottom-right cell path sums. This results in the following recurrence:
T[i][j] = mat[i][j] + min(T[i+1][j], T[i+1][j+1])
For instance, using the recurrence described above, the matrix to the left will produce the table to the right. The shortest path has the total 9 and is [4, 3, 1, 1].
[4] [9, 0, 0, 0]
[1, 3] —> [6, 5, 0, 0]
[1, 2, 1] [5, 6, 2, 0]
[8, 4, 5, 1] [8, 4, 5, 1]
The implementation can be seen below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include #include using namespace std;
int getMinimumValue(vector<vector<int>> const &mat) { int N = mat.size();
// take a `N x N` matrix to store the subproblem solutions vector<vector<int>> T(N, vector<int>(N));
// initialize the last row of the DP matrix with the last row of the matrix T[N–1] = mat.back();
// start from the second last row for (int row = N – 2; row >= 0; row—) { // compute T[] for each entry of the current row for (int col = 0; col <= row; col++) { // T[row][col] would be sum of the current element, and // the minimum of its bottom and bottom-right cell T[row][col] = mat[row][col] + min(T[row+1][col], T[row+1][col+1]); } }
return T[0][0]; }
int main() { vector<vector<int>> mat = { {4}, {1, 3}, {1, 2, 1}, {8, 4, 5, 1} };
cout << getMinimumValue(mat);
return 0; } |
Output:
9
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import java.util.Arrays;
class Main { public static int getMinimumValue(int[][] mat) { int N = mat.length;
// take a `N x N` matrix to store the subproblem solutions int[][] T = new int[N][N];
// initialize the last row of the DP matrix with the last row of the matrix T[N–1] = Arrays.copyOf(mat[N–1], N);
// start from the second last row for (int row = N – 2; row >= 0; row—) { // compute T[] for each entry of the current row for (int col = 0; col <= row; col++) { // T[row][col] would be sum of the current element, and // the minimum of its bottom and bottom-right cell T[row][col] = mat[row][col] + Integer.min(T[row+1][col], T[row+1][col+1]); } }
return T[0][0]; }
public static void main(String[] args) { int[][] mat = { {4}, {1, 3}, {1, 2, 1}, {8, 4, 5, 1} };
System.out.println(getMinimumValue(mat)); } } |
Output:
9
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
def getMinimumValue(mat): # take a matrix to store the subproblem solutions T = [[0 for x in range(len(mat))] for y in range(len(mat))]
# initialize the last row of the DP matrix with the last row of the matrix T[–1] = mat[–1]
# start from the second last row for row in reversed(range(0, len(mat) – 1)): # compute T[] for each entry of the current row for col in range(0, row + 1): # T[row][col] would be sum of the current element, and # the minimum of its bottom and bottom-right cell T[row][col] = mat[row][col] + min(T[row + 1][col], T[row + 1][col + 1])
return T[0][0]
if __name__ == ‘__main__’: mat = [ [4], [1, 3], [1, 2, 1], [8, 4, 5, 1] ] print(getMinimumValue(mat))
|
Output:
9
The time complexity of the above solution is O(N × N) and requires O(N × N) extra space, where N is the number of rows in the matrix.
Take note of the bottom-up filling of the T[][] table. As we are always reading from the subsequent row of the current row, the space complexity of the solution can be reduced to O(N). The space-optimized algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include #include using namespace std;
int getMinimumValue(vector<vector<int>> const &mat) { // initialize the DP array with the last row vector<int> T(mat.back());
// start from the second last row for (int row = mat.size() – 2; row >= 0; row—) { // compute T[] for each entry of the current row for (int col = 0; col <= row; col++) { // T[col] would be sum of the current element, and // the minimum of its bottom and bottom-right cell T[col] = mat[row][col] + min(T[col], T[col + 1]); } }
return T[0]; }
int main() { vector<vector<int>> mat = { {4}, {1, 3}, {1, 2, 1}, {8, 4, 5, 1} };
cout << getMinimumValue(mat);
return 0; } |
Output:
9
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.Arrays;
class Main { public static int getMinimumValue(int[][] mat) { int N = mat.length;
// initialize the DP array with the last row int[] T = Arrays.copyOf(mat[N–1], N);
// start from the second last row for (int row = N–2; row >= 0; row—) { // compute T[] for each entry of the current row for (int col = 0; col <= row; col++) { // T[col] would be sum of the current element, and // the minimum of its bottom and bottom-right cell T[col] = mat[row][col] + Integer.min(T[col], T[col + 1]); } }
return T[0]; }
public static void main(String[] args) { int[][] mat = { {4}, {1, 3}, {1, 2, 1}, {8, 4, 5, 1} };
System.out.println(getMinimumValue(mat)); } } |
Output:
9
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def getMinimumValue(mat): # initialize the DP array with the last row T = mat[–1]
# start from the second last row for row in reversed(range(0, len(mat) – 1)): # compute T[] for each entry of the current row for col in range(0, row + 1): # T[col] would be sum of the current element, and # the minimum of its bottom and bottom-right cell T[col] = mat[row][col] + min(T[col], T[col + 1])
return T[0]
if __name__ == ‘__main__’: mat = [ [4], [1, 3], [1, 2, 1], [8, 4, 5, 1] ] print(getMinimumValue(mat))
|
Output:
9
The time complexity of the above solution is O(N × N) and requires O(N) extra space, where N is the number of rows in the matrix.
Credit goes to the respective owner!