Title / Description
Code 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); }
Author
Highlight as C C++ CSS Clojure Delphi ERb Groovy (beta) HAML HTML JSON Java JavaScript PHP Plain text Python Ruby SQL XML YAML diff code
1.1.2
1.1.2