DP #23. Minimum Cost Path. - mbhushan/dynpro GitHub Wiki
(23). Minimum Cost Path.
Given a 2 dimensional matrix, find minimum cost path to reach bottom right
from top left provided you can only from down and right.
Formula:
T[0][0] = M[0][0]
First Row:
T[0][i] = T[0][i-1] + M[0][i]
First Col:
T[i][0] = T[i-1][0] + M[i][0]
Formula:
For (int i=1; i<row; i++) {
For (int j=1; j<col; j++) {
T[i][j] = M[i][j] + Math.min(T[i-1][j], T[i][j-1], T[i-1][j-1])
}
}
| input -> |
1 |
2 |
3 |
|
4 |
8 |
2 |
|
1 |
5 |
3 |
|
|
|
|
| T [][] -> |
1 |
3 |
6 |
|
5 |
9 |
5 |
|
6 |
10 |
8 (ans) |
Minimum Cost Path
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)