Dynamic programming can be applied in minimum cost path problems. In this article, we are going to discuss two common minimum cost path problems.

Problem 1:

Given a matrix of size MxN where every cell has a cost associated with it. We need to find the minimum cost to reach the last cell (m,n) from (0,0). You can move only one unit down or one unit right from any cell i.e. from a cell (i,j) you can move to (i+1,j) or (i,j+1).

Example:

1	2	3
4	8	2
1	5	3

 

Answer: The path with minimum cost is (0,0) -> (0,1) -> (0,2) -> (1,1) -> (1,2). The cost of this path is 1+2+3+2+3 = 11.

We are going to use a recursion for solving this problem. This problem has optimal substructure. Thus, we can break this problem into smaller and simple subproblems. We need to find the min(path going down, the path going right). We can recursively define this problem as:            

Cost to reach cell (m,n) = cost[m][n] + min(cost to reach(m,n-1) , cost to reach(m-1,n)

 

You can check the code below.

O/P:

The minimum cost path is 11

 

The time complexity of this solution is going to be (2ⁿ) or exponential. This solution is going to compute the same subproblems multiple times. You can see in the recursion tree that most nodes are repeating. Thus, this solution is actually very slow. Recursion tree for minCostPath(2):

                             (2,2)                                          /      \                                             (1,2)     (2,1)                               /     \     /     \                                (0,2)  (1,1) (1,1)  (2,0)          

This problem has both optimal substructure and overlapping subproblems. Thus, we can use the DP approach for solving this problem. We can store the result for subproblem. This will ensure that subproblems won’t be recomputed.

At every cell, we can either go down or right. We will always move towards the minimum of these two cells. For any i,j cell:

dp[i][j] = dp[i][j] + min(dp[i-1][j],dp[i][j-1]) for all i>0&&j>0

You can check the code below.

O/P:

The minimum cost path is 11

O/P: The minimum cost path is 11

 

The time complexity and space complexity of this solution is O(nxm).

Problem 2: Given a matrix of size MxN where every cell has a cost associated with it. We need to find the minimum cost to reach the last cell (m,n) from (0,0). You can move only one unit down, one unit right, and to diagonally lower cells from any cell i.e. from a cell (i,j) you can move to (i+1,j),(i,j+1), and (i+1,j+1).

Example:

1	9	4
4	7	5
2	9	1

Answer: The path with minimum cost is (0,0) -> (1,1) -> (2,2). The cost of this path is 1+7+1 = 9.

This problem is very similar to the problem that we have just discussed. However, we can move to three different cells this time. We can reach (m,n) only through these cells: (m,n-1) or (m-1,n) or (m-1,n-1). We need to find the minimum of these 3 cells and add them to the cost of (m,n) cell. Thus, the recurrence relation is:

Cost to reach cell (m,n) = cost[m][n] + min(cost to reach(m,n-1) , cost to reach(m-1,n),cost to reach(m-1,n-1))

You can check the code below.

O/P: The minimum cost path is 9 

This problem also has both optimal substructure and overlapping subproblems. Thus, we can use the DP approach for solving this problem. We will use a dp[][] array for storing subproblem results. You can check the code below.

O/P

: The minimum cost path is 9 

The time and space complexity of this solution is also O(n*m).