Skip to content

Instantly share code, notes, and snippets.

@addamh
Created November 18, 2013 18:24
Show Gist options
  • Save addamh/7532759 to your computer and use it in GitHub Desktop.
Save addamh/7532759 to your computer and use it in GitHub Desktop.
int distance = 10;
int numberOfTiles = 2;
int[] length = {1, 5};
int[] cost = {1, 4};
int cheapest = cheapest(distance, numberOfTiles, length, cost);
public static int cheapest(int distance, int numberOfTiles, int[] length, int[] cost) {
int[] c = new int[numberOfTiles];
int min = 0;
for (int p = 1; p <= distance; p++) {
for (int i = 1; i <= numberOfTiles; i++) {
if(cost[i] <= p){
if(cost[i] + c[p - length[i]] < min){
min = cost[i] + c[p - length[i]];
}
}
}
c[p] = min;
}
return c[numberOfTiles];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment