java

public ArrayList<Integer> rodCut(int A, ArrayList<Integer> B) {
  B.add(0, 0);
  B.add(A);
  int size = B.size();
  long[][] cost = new long[size][size];
  int[][] index = new int[size][size];
  for (long[] arr : cost)
    Arrays.fill(arr, -1);
  for (int i = 0; i < size - 1; i++) {
    cost[i][i + 1] = 0;
  }

  for (int length = 2; length <= size - 1; length++) {
    for (int i = 0; i < size - length; i++) {
      int j = i + length;
      long firstCut = ((long)B.get(j) - B.get(i));
      cost[i][j] = cost[i][i + 1] + cost[i + 1][j] + firstCut;
      index[i][j] = i + 1;
      for (int k = i + 2; k < j; k++) {
        long new_cost = cost[i][k] + cost[k][j] + firstCut;
        if (new_cost < cost[i][j]) {
          cost[i][j] = new_cost;
          index[i][j] = k;
        }
      }
    }
  }
  ArrayList<Integer> result = new ArrayList<>();
  backtracking(0, size - 1, index, result, B);
  return result;
}

public void backtracking(int i, int j, int[][] index, ArrayList<Integer> result, ArrayList<Integer> B) {
  if (i >= j - 1) return;
  int lowest = index[i][j];
  result.add(B.get(lowest));
  backtracking(i, lowest, index, result, B);
  backtracking(lowest, j, index, result, B);
}