Dynamic Programming in Go #3: Minimum Cost Path
In this series ‘Dynamic Programming in Go’, we discuss various solutions using DP and come across concepts as we go.
In the previous post we discussed a concept called ‘Tabulation’: https://hitesh-pattanayak.medium.com/dynamic-programming-in-go-2-climbing-stairs-46597d61157c
In a post prior to that we discussed a concept called ‘Memoization’: https://hitesh-pattanayak.medium.com/dynamic-programming-in-go-1-fibonacci-68d2b7f1b616
In this Solution, we will reiterate on ‘Tabulation’.
As we already know, Tabulation has 3 aspects:
- Storage and Meaning
- Travel and Solve
Given a matrix, find the minimum cost to travel from source (first cell) to destination (last cell). Each cell of the matrix has the cost to pass through it.
Initial Solution matrix
- Each cell represent cost to travel from that cell to last cell.
- Direction: we will start from last cell -> last column (right to left) -> second last column and so on.
- Every time we reach a cell, we will find cost from that cell by looking in all possible 4 directions.
- The last cell already has ‘2’ because minimum cost to travel from last cell to the last cell is the value of the last cell itself.
Final Solution Matrix
Code & Test
Please check for new stories on ‘Dynamic Programming in Go’.
Also do check out previous articles of this series.
Folks, if you like my content, would you consider following me on linked in at: https://www.linkedin.com/in/hitesh-pattanayak-52290b160/