Min cost path using Dynamic Programming(Space optimized)
To solve the problem follow the below idea:
The idea is to use the same given/input array to store the solutions of subproblems in the above solution
Follow the below steps to solve the problem:
- Calculate prefix sum for the first row and first column in ‘cost’ array as there is only one way to reach any cell in the first row or column
- Run a nested for loop for i [1, M-1] and j [1, N-1]
- Set cost[i][j] equal to minimum of (cost[i-1][j-1], cost[i-1][j], cost[i][j-1]) + cost[i][j]
- Return cost[M-1][N-1]
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define row 3#define col 3int minCost(int cost[row][col]){ // for 1st column for (int i = 1; i < row; i++) cost[i][0] += cost[i - 1][0]; // for 1st row for (int j = 1; j < col; j++) cost[0][j] += cost[0][j - 1]; // for rest of the 2d matrix for (int i = 1; i < row; i++) for (int j = 1; j < col; j++) cost[i][j] += min(cost[i - 1][j - 1], min(cost[i - 1][j], cost[i][j - 1])); // returning the value in last cell return cost[row - 1][col - 1];}// Driver codeint main(int argc, char const* argv[]){ int cost[row][col] = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; cout << minCost(cost) << endl; return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
C
// C++ program for the above approach#include <stdio.h>#define row 3#define col 3// Find minimum between two numbers.int min(int num1, int num2){ return (num1 > num2) ? num2 : num1;}int minCost(int cost[row][col]){ // for 1st column for (int i = 1; i < row; i++) cost[i][0] += cost[i - 1][0]; // for 1st row for (int j = 1; j < col; j++) cost[0][j] += cost[0][j - 1]; // for rest of the 2d matrix for (int i = 1; i < row; i++) for (int j = 1; j < col; j++) cost[i][j] += min(cost[i - 1][j - 1], min(cost[i - 1][j], cost[i][j - 1])); // returning the value in last cell return cost[row - 1][col - 1];}// Driver codeint main(){ int cost[row][col] = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; printf("%d \n", minCost(cost)); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program for the// above approachimport java.util.*;class GFG { static int row = 3; static int col = 3; static int minCost(int cost[][]) { // for 1st column for (int i = 1; i < row; i++) { cost[i][0] += cost[i - 1][0]; } // for 1st row for (int j = 1; j < col; j++) { cost[0][j] += cost[0][j - 1]; } // for rest of the 2d matrix for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { cost[i][j] += Math.min(cost[i - 1][j - 1], Math.min(cost[i - 1][j], cost[i][j - 1])); } } // Returning the value in // last cell return cost[row - 1][col - 1]; } // Driver code public static void main(String[] args) { int cost[][] = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; System.out.print(minCost(cost) + "\n"); }}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the# above approachdef minCost(cost, row, col): # For 1st column for i in range(1, row): cost[i][0] += cost[i - 1][0] # For 1st row for j in range(1, col): cost[0][j] += cost[0][j - 1] # For rest of the 2d matrix for i in range(1, row): for j in range(1, col): cost[i][j] += (min(cost[i - 1][j - 1], min(cost[i - 1][j], cost[i][j - 1]))) # Returning the value in # last cell return cost[row - 1][col - 1]# Driver codeif __name__ == '__main__': row = 3 col = 3 cost = [[1, 2, 3], [4, 8, 2], [1, 5, 3]] print(minCost(cost, row, col))# This code is contributed by Amit Katiyar |
C#
// C# program for the// above approachusing System;class GFG { static int row = 3; static int col = 3; static int minCost(int[, ] cost) { // for 1st column for (int i = 1; i < row; i++) { cost[i, 0] += cost[i - 1, 0]; } // for 1st row for (int j = 1; j < col; j++) { cost[0, j] += cost[0, j - 1]; } // for rest of the 2d matrix for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { cost[i, j] += Math.Min(cost[i - 1, j - 1], Math.Min(cost[i - 1, j], cost[i, j - 1])); } } // Returning the value in // last cell return cost[row - 1, col - 1]; } // Driver code public static void Main(String[] args) { int[, ] cost = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; Console.Write(minCost(cost) + "\n"); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program for the // above approachvar row = 3; var col = 3; function minCost(cost) { // for 1st column for (i = 1; i < row; i++) { cost[i][0] += cost[i - 1][0]; } // for 1st row for (j = 1; j < col; j++) { cost[0][j] += cost[0][j - 1]; } // for rest of the 2d matrix for (i = 1; i < row; i++) { for (j = 1; j < col; j++) { cost[i][j] += Math.min(cost[i - 1][j - 1], Math.min(cost[i - 1][j], cost[i][j - 1])); } } // Returning the value in // last cell return cost[row - 1][col - 1]; } // Driver code var cost = [[1, 2, 3], [4, 8, 2], [1, 5, 3] ]; document.write(minCost(cost) + '<br>'); // This code is contributed by 29AjayKumar </script> |
Output
8
Time Complexity: O(N * M), where N is the number of rows and M is the number of columns
Auxiliary Space: O(1), since no extra space has been taken
Min Cost Path | DP-6
Given a cost matrix cost[][] and a position (M, N) in cost[][], write a function that returns cost of minimum cost path to reach (M, N) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. The total cost of a path to reach (M, N) is the sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1), and (i+1, j+1) can be traversed.
Note: You may assume that all costs are positive integers.
Example:
Input:
The path with minimum cost is highlighted in the following figure. The path is (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).
Output: