Min cost path using Memoization DP
To convert the given recursive implementation to a memoized version, use an auxiliary table to store the already computed values.
An additional 2D array memo is introduced to store the computed values. Initially, all entries of memo are set to -1 using the memset function. The minCostMemoized function is recursively called, and before making a recursive call, it checks if the value has already been computed by checking the corresponding entry in the memo table. If the value is found in the memo table, it is directly returned. Otherwise, the value is computed, stored in the memo table, and returned.
This memoized version will avoid redundant recursive calls and greatly improve the efficiency of the algorithm by storing and reusing previously computed values.
C++
// A Dynamic Programming based// solution for MCP problem#include <bits/stdc++.h>using namespace std;#define R 3#define C 3int min(int x, int y, int z);// Returns cost of minimum cost path// from (0,0) to (m, n) in mat[R][C]int minCostMemoized(int cost[R][C], int m, int n, int memo[R][C]){ if (n < 0 || m < 0) return INT_MAX; else if (m == 0 && n == 0) return cost[m][n]; if (memo[m][n] != -1) return memo[m][n]; memo[m][n] = cost[m][n] + min(minCostMemoized(cost, m - 1, n - 1, memo), minCostMemoized(cost, m - 1, n, memo), minCostMemoized(cost, m, n - 1, memo)); return memo[m][n];}// Returns cost of minimum cost path// from (0,0) to (m, n) in mat[R][C]int minCost(int cost[R][C], int m, int n){ int memo[R][C]; memset(memo, -1, sizeof(memo)); // Initialize memo table with -1 return minCostMemoized(cost, m, n, memo);}// A utility function that returns// minimum of 3 integersint min(int x, int y, int z){ if (x < y) return (x < z) ? x : z; else return (y < z) ? y : z;}// Driver codeint main(){ int cost[R][C] = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; cout << minCost(cost, 2, 2) << endl; return 0;} |
Java
import java.util.Arrays;public class MinimumCostPath { // Define the number of rows and columns static final int R = 3; static final int C = 3; // Utility function to find the minimum of three integers public static int min(int x, int y, int z) { if (x < y) return (x < z) ? x : z; else return (y < z) ? y : z; } // Recursive function to find the minimum cost path using memoization public static int minCostMemoized(int[][] cost, int m, int n, int[][] memo) { // Base case: if out of bounds, return a large value (to be ignored) if (n < 0 || m < 0) return Integer.MAX_VALUE; // Base case: if at the top-left corner, return the cost at that cell else if (m == 0 && n == 0) return cost[m][n]; // Check if the result is already memoized if (memo[m][n] != -1) return memo[m][n]; // Calculate the minimum cost to reach the current cell memo[m][n] = cost[m][n] + min(minCostMemoized(cost, m - 1, n - 1, memo), minCostMemoized(cost, m - 1, n, memo), minCostMemoized(cost, m, n - 1, memo)); // Return the minimum cost return memo[m][n]; } // Function to find the minimum cost path from (0, 0) to (m, n) public static int minCost(int[][] cost, int m, int n) { // Create a memoization table to store intermediate results int[][] memo = new int[R][C]; for (int[] row : memo) Arrays.fill(row, -1); // Initialize memo table with -1 // Call the memoized function to find the minimum cost return minCostMemoized(cost, m, n, memo); } public static void main(String[] args) { // Cost matrix for the grid int[][] cost = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; // Calculate and print the minimum cost path from (0, 0) to (2, 2) System.out.println(minCost(cost, 2, 2)); }} |
Python3
R = 3C = 3# Returns cost of minimum cost path# from (0,0) to (m, n) in mat[R][C]def min_cost_memoized(cost, m, n, memo): if n < 0 or m < 0: return float('inf') elif m == 0 and n == 0: return cost[m][n] if memo[m][n] != -1: return memo[m][n] memo[m][n] = cost[m][n] + min( min_cost_memoized(cost, m - 1, n - 1, memo), min_cost_memoized(cost, m - 1, n, memo), min_cost_memoized(cost, m, n - 1, memo) ) return memo[m][n]# Returns cost of minimum cost path# from (0,0) to (m, n) in mat[R][C]def min_cost(cost, m, n): memo = [[-1] * C for _ in range(R)] # Initialize memo table with -1 return min_cost_memoized(cost, m, n, memo)# Driver codecost = [ [1, 2, 3], [4, 8, 2], [1, 5, 3]]print(min_cost(cost, 2, 2)) |
C#
using System;class Program { const int R = 3; const int C = 3; // Returns cost of minimum cost path // from (0,0) to (m, n) in mat[R][C] static int MinCostMemoized(int[][] cost, int m, int n, int[][] memo) { if (n < 0 || m < 0) return int.MaxValue; else if (m == 0 && n == 0) return cost[m][n]; if (memo[m][n] != -1) return memo[m][n]; memo[m][n] = cost[m][n] + Math.Min( Math.Min(MinCostMemoized(cost, m - 1, n - 1, memo), MinCostMemoized(cost, m - 1, n, memo)), MinCostMemoized(cost, m, n - 1, memo)); return memo[m][n]; } // Returns cost of minimum cost path // from (0,0) to (m, n) in mat[R][C] static int MinCost(int[][] cost, int m, int n) { int[][] memo = new int[R][]; for (int i = 0; i < R; i++) { memo[i] = new int[C]; for (int j = 0; j < C; j++) { memo[i][j] = -1; } } return MinCostMemoized(cost, m, n, memo); } // A utility function that returns // minimum of 3 integers static int Min(int x, int y, int z) { if (x < y) return (x < z) ? x : z; else return (y < z) ? y : z; } // Driver code static void Main(string[] args) { int[][] cost = new int[][] { new int[] { 1, 2, 3 }, new int[] { 4, 8, 2 }, new int[] { 1, 5, 3 } }; Console.WriteLine(MinCost(cost, 2, 2)); // Output: 8 }} |
Javascript
const R = 3;const C = 3;// Helper function to find the minimum of three integersfunction min(x, y, z) { return (x < y) ? (x < z ? x : z) : (y < z ? y : z);}// Function to calculate the minimum cost path using memoizationfunction minCostMemoized(cost, m, n, memo) { // Base case: if we're outside the grid, return a large value if (n < 0 || m < 0) { return Number.MAX_SAFE_INTEGER; } // Base case: if we're at the top-left cell, return its cost else if (m === 0 && n === 0) { return cost[m][n]; } // If the result is already computed, return it if (memo[m][n] !== -1) { return memo[m][n]; } // Calculate the cost for the current cell and store it in the memo table memo[m][n] = cost[m][n] + min( minCostMemoized(cost, m - 1, n - 1, memo), // Diagonal minCostMemoized(cost, m - 1, n, memo), // Up minCostMemoized(cost, m, n - 1, memo) // Left ); return memo[m][n];}// Function to find the minimum cost path from (0,0) to (m, n)function minCost(cost, m, n) { // Initialize a memoization table filled with -1 const memo = new Array(R).fill().map(() => new Array(C).fill(-1)); // Call the memoized function to compute the result return minCostMemoized(cost, m, n, memo);}// Input matrix of costsconst cost = [ [1, 2, 3], [4, 8, 2], [1, 5, 3]];// Calculate and print the minimum cost pathconsole.log(minCost(cost, 2, 2)); |
Time Complexity: O(M * N)
Auxiliary Space: O(M * N)
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: