-
Notifications
You must be signed in to change notification settings - Fork 0
/
Cutting Wood I.java
39 lines (36 loc) · 1.36 KB
/
Cutting Wood I.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
There is a wooden stick with length L >= 1, we need to cut it into pieces,
where the cutting positions are defined in an int array A. The positions are guaranteed
to be in ascending order in the range of [1, L - 1]. The cost of each cut is the length
of the stick segment being cut. Determine the minimum total cost to cut the stick into the defined pieces.
Examples
L = 10, A = {2, 4, 7}, the minimum total cost is 10 + 4 + 6 = 20 (cut at 4 first then cut at 2 and cut at 7)
time = O(n^3)
space = O(n^2)
*/
public class Solution {
public int minCost(int[] cuts, int length) {
int[] helper = new int[cuts.length + 2];
helper[0] = 0;
for (int i = 1; i < cuts.length; i++) {
helper[i + 1] = cuts[i];
}
helper[helper.length - 1] = length;
// min cost of cutting (i, j)
int[][] cost = new int[helper.length][helper.length];
for (int i = 1; i < helper.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (j + 1 == i) {
cost[j][i] = 0;
} else {
cost[j][i] = Integer.MAX_VALUE;
for (int k = j + 1; k < i; k++) {
cost[j][i] = Math.min(cost[j][i], cost[j][k] + cost[k][i]);
}
cost[j][i] += helper[i] - helper[j];
}
}
}
return cost[0][helper.length - 1];
}
}