6. Minimum Cost #

Created Thursday 02 July 2020

• In DP problems, we do need multidimensional arrays. Dimension = number of state parameters.
• Finding the answer to this problem. We start from the top-left and go to the bottom-right.

• We can say f(i, j) = min(f(i+1, j)+f(i+1, j+1)+f(i, j+1))
• There’s a lot of repeated work.
• As movement is to the R,D or RD - the answer for any cell depends its L, U and LU. This makes a bottom-up approach possible, as only previous problems decide the current problem.
• We’ll need a 2D array - i and j uniquely identify the cell: Path starting from i, j. Previous path does not matter.
• For borders cost is ∞, so they rejected.
• Time O(n^2^), Space O(n^2^)

Iterative Solution #

• Each value depends on R, D and RD.
• The destination value = destination_value, because it has no R, D or RD.
• We can fill the one above the destination, because it has only D, R and RD are absent. Value = current+down.
• We can full the one on the left of the destination, because it has no D or RD. Has only R. Value = current+right.
• This can be filled directly.
• After this we fill the LT of the destination, which has all prerequisites fullfilled.
• This way, in RLDT we will arrive at the staring point. Which will have the value of the minimum cost. Done.