Skip to content

Instantly share code, notes, and snippets.

@sdpatil
Last active August 13, 2017 00:08
Show Gist options
  • Save sdpatil/c0a727ba3f4278e71c2b18e3bbeb09b2 to your computer and use it in GitHub Desktop.
Save sdpatil/c0a727ba3f4278e71c2b18e3bbeb09b2 to your computer and use it in GitHub Desktop.
Minimum cost to travel from one station to another
import java.util.Arrays;
/*
Problem: Given cost of ticket for each station from A to B as 2 dimensional matrix
what is the minimum cost that you can use to travel
*/
public class MinTicketCost {
public static void main(String[] argv) {
int[][] cost = {
{0, 10, 75, 94},
{-1, 0, 35, 50},
{-1, -1, 0, 80},
{-1, -1, -1, 0}
};
/* // System.out.println("Minimum cost " +calculateMinCost(cost,0,3));
int[][] minCost = new int[cost.length][cost[0].length];
System.out.println("Minimum cost " + calculateMinCostMemorization(cost, 0, 3, minCost));
for (int[] row : minCost)
System.out.println(Arrays.toString(row));
*/
System.out.println("Minimum cost " + calculateMinCostDP(cost,0,3));
}
/*
Solution: To solve this problem basic idea would be to recursively calculate cost between
Source to 1 and 1 to desination or source to 2 and 2 desitnation
*/
public static int calculateMinCost(int[][] cost, int source, int destination) {
System.out.println("Source " + source + " Destination " + destination);
if (source == destination || source == destination - 1)
return cost[source][destination];
int minCost = cost[source][destination];
for (int i = source + 1; i < destination; i++) {
int temp = calculateMinCost(cost, source, i) +
calculateMinCost(cost, i, destination);
System.out.println("After recursion");
if (temp < minCost)
minCost = temp;
}
return minCost;
}
/*
This is memorization version of the problem
*/
public static int calculateMinCostMemorization(int[][] cost, int source, int destination, int[][] mCost) {
if (source == destination || source == destination - 1)
return cost[source][destination];
if (mCost[source][destination] != 0)
return mCost[source][destination];
System.out.println("Source " + source + " Destination " + destination);
int minCost = cost[source][destination];
for (int i = source + 1; i < destination; i++) {
int temp = calculateMinCostMemorization(cost, source, i, mCost) +
calculateMinCostMemorization(cost, i, destination, mCost);
System.out.println("After recursion");
if (temp < minCost)
minCost = temp;
}
mCost[source][destination] = minCost;
return minCost;
}
// This is DP version of the solution
public static int calculateMinCostDP(int[][] cost, int source, int destination) {
int[] minCost = new int[cost.length];
minCost[0] = 0;
minCost[1] = cost[source][1];
for(int i = 2 ; i < cost.length ; i++ ){
minCost[i] = cost[0][i];
for(int j = 1; j < i ;j++) {
minCost[i] = Math.min(minCost[i], minCost[j] + cost[j][i]);
}
}
System.out.println(Arrays.toString(minCost));
return minCost[destination];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment