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...

  • Rahul Shukla

    http://www.ideserve.co.in/learn/minimum-cost-path
    Here is a nice detailed expla­na­tion of the algorithm.

  • Red

    I believe the answer is 14, not 29. Can you check? I get that when I run it man­u­ally and with the program.

    Also for the fol­low­ing, why are you set­ting 0,0 first rather than set­ting the first row with i=0 to length and first col­umn with i = 0 to length? I think when you do i=1, you are set­ting the val­ues of the sec­ond row and sec­ond col­umn. How can solution[0,i-1] even have a value if you haven’t ini­tial­ized it yet? e.g. for solution[0, 2]

    solution[0][0] = A[0][0];
    // fill the first row
    for (int i = 1; i < A.length; i++) {
    solution[0][i] = A[0][i] + solution[0][i — 1];
    }

    // fill the first col­umn
    for (int i = 1; i < A.length; i++) {
    solution[i][0] = A[i][0] + solution[i — 1][0];
    }

    • Red

      I tried this and it worked:

      pub­lic sta­tic void Min­Cost­Path()
      {
      int[,] arr = new int[,] { { 1, 7, 9, 2 },
      { 8, 6, 3, 2 },
      { 1, 6, 7, 8 },
      { 2, 9, 8, 2 } };

      int[,] solu­tion = new int[arr.GetLength(0), arr.GetLength(1)];

      for (int row = 0; row < arr.GetLength(0); row++)
      {
      solution[row, 0] = arr[row, 0];
      }

      for (int col = 0; col < arr.GetLength(1); col++)
      {
      solution[0, col] = arr[0, col];
      }

      for (int row = 1; row < arr.GetLength(1); row++)
      {
      for (int col = 1; col < arr.GetLength(0); col++)
      {
      solution[row, col] = arr[row, col] + Math.Min(solution[row — 1, col], solution[row, col — 1]);
      }
      }

      Console.WriteLine(“Minimum cost of trav­el­ing through the array is: {0}”, solution[solution.GetLength(0)-1, solution.GetLength(1)-1]);
      }

    • tuto­ri­al­hori­zon

      when you say answer is 14, whats the path