/******************************************************************************
Online Java Compiler.
Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.
*******************************************************************************/
import java.util.*;
public class Main
{
public static void main(String[] args) {
int[] brokenCabins = {20, 30, 75, 80};
System.out.println(minTape(4, 100, 2, brokenCabins));
}
public static int minTape(int numBrokenCabins, int totalCabins, int numTapeCuts, int[] brokenCabins){
int firstCabin = brokenCabins[0];
int maxLength = brokenCabins[brokenCabins.length-1] - firstCabin + 1;
int minLength = maxLength;
// Base cases
if(numTapeCuts == 1){
return maxLength;
}
if(numTapeCuts == numBrokenCabins){
return numBrokenCabins;
}
for(int i = 0; i < brokenCabins.length-1; i++){
int currentCabin = brokenCabins[i];
int thisLength = currentCabin - firstCabin + 1;
int newNumBrokenCabins = numBrokenCabins - i - 1;
int newTotalCabins = totalCabins;
int newNumTapeCuts = numTapeCuts - 1;
int[] newBrokenCabins = Arrays.copyOfRange(brokenCabins, i+1, brokenCabins.length);
if(newNumBrokenCabins < newNumTapeCuts){
break;
}
int totalLength = thisLength + minTape(newNumBrokenCabins, newTotalCabins, newNumTapeCuts, newBrokenCabins);
minLength = totalLength < minLength ? totalLength : minLength;
}
return minLength;
}
}
