Be the first user to complete this post

Add to List 
Dynamic Programming  Minimum Cost Path Problem
Objective: Given a 2D matrix where each cell has a cost to travel. You have to write an algorithm to find a path from the lefttop corner to the bottomright corner with minimum travel cost. You can move only right or down.
In the solution, we will see how dynamic programming is a much better to approach than recursion. Don't get me wrong, even I like recursion a lot :)
Example:
Approach:
This problem is similar to Find all paths from topleft corner to bottomright corner.
We can solve it using Recursion ( return Min(path going right, path going down)) but that won't be a good solution because we will be solving many subproblems multiple times. Since at every cell we have 2 options the time complexity will be O(2^{n}).
Dynamic Programming:
Create a solution matrix of the same size as a given matrix.
We will fill this matrix in Bottomup manner.
Given: arrA[][].
At every cell, we have two options (go right or down) and we will choose the minimum of these two. So for any i,j cell solution[i][j] = A[0][j] if i=0 , first row = A[i][0] if j=0, first column = A[i][j] + Min(solution[i1],[j] , solution[i][j1]) if i>0 && j>0 See the code for better Explanation.
Time Complexity: O(n^{2}).
Code:
Output
: Minimum Cost Path 29
Also Read: