Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Minimum Cost Path Problem

Objec­tive: Given a 2D-matrix where each cell has a cost to travel. You have to write an algo­rithm to find a path from left-top cor­ner to bottom-right cor­ner with min­i­mum travel cost. You can move only right or down.

In the solu­tion we will see that how dynamic pro­gram­ming is much bet­ter approach than recur­sion. Don’t get me wrong, even I like recur­sion a lot 🙂

Exam­ple:

MInimum-Cost-Path-Problem

MInimum-Cost-Path-Problem

Approach:

This prob­lem is sim­i­lar to Find all paths from top-left cor­ner to bottom-right cor­ner.

We can solve it using Recur­sion ( return Min(path going right, path going down)) but that won’t be a good solu­tion because we will be solv­ing many sub-problems mul­ti­ple times. Since at every cell we have 2 options the time com­plex­ity will O(2n).

Dynamic Pro­gram­ming:

Cre­ate a solu­tion matrix of the same size as given matrix.

We will fill this matrix in Bottom-up 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[i-1],[j] , solution[i][j-1]) if i>0 && j>0

See the code for better Explanation.

Time Com­plex­ity: O(n2).

Code:

Output:
Minimum Cost Path 29

You may also like...