Min cost path by means of memoizing DP: We utilize a 2D array for memorizing since the recursive solution changes two parameters.
To signify that no values are computed initially, we start the 2D array as -1.
First we check in the memo table in the recursion. Should we detect value as -1, we only call recursively. In this sense, we avoid recommendations of the same sub-problems.
C++
#include <bits/stdc++.h>
using namespace std;
// Returns the cost of the minimum cost path from
// (0,0) to (m, n) in the cost matrix
int minCostMemo(vector<vector<int>>& cost, int m, int n,
vector<vector<int>>& memo) {
if (m < 0 || n < 0)
return INT_MAX;
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({minCostMemo(cost, m - 1, n - 1, memo),
minCostMemo(cost, m - 1, n, memo),
minCostMemo(cost, m, n - 1, memo)});
return memo[m][n];
}
int minCost(vector<vector<int>>& cost, int m, int n) {
// Initialize memo table with -1
vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
return minCostMemo(cost, m, n, memo);
}
// Driver code
int main() {
vector<vector<int>> cost = { { 1, 2, 3 },
{ 4, 8, 2 },
{ 1, 5, 3 } };
cout << "Minimum cost: " << 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));
}
}Python
R = 3
C = 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 code
cost = [
[1, 2, 3],
[4, 8, 2],
[1, 5, 3]
]
print(min_cost(cost, 2, 2))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 integers
function min(x, y, z) {
return (x < y) ? (x < z ? x : z) : (y < z ? y : z);
}
// Function to calculate the minimum cost path using memoization
function 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 costs
const cost = [
[1, 2, 3],
[4, 8, 2],
[1, 5, 3]
];
// Calculate and print the minimum cost path
console.log(minCost(cost, 2, 2));Time Complexity:Â O(M * N)
Auxiliary Space:Â O(M * N)