/
MinimumCostToCutAStick.java
30 lines (26 loc) · 1.09 KB
/
MinimumCostToCutAStick.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
// https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
class Solution {
public int minCost(int n, int[] cuts) {
boolean[] v = new boolean[cuts.length];
Map<Long, Integer> memo = new HashMap<>();
return min(cuts, 0, n, v, memo);
}
int min(int[] cuts, int start, int end, boolean[] visited, Map<Long, Integer> memo) {
int score = 0;
long key = start * 10000000 + end;
if (memo.containsKey(key)) return memo.get(key);
for (int i = 0; i < cuts.length; i++) {
if (!visited[i] && cuts[i] > start && cuts[i] < end) {
visited[i] = true;
if (score == 0) {
score = (end - start) + min(cuts, start, cuts[i], visited, memo) + min(cuts, cuts[i], end, visited, memo);
} else {
score = Math.min(score, (end - start) + min(cuts, start, cuts[i], visited, memo) + min(cuts, cuts[i], end, visited, memo));
}
visited[i] = false;
}
}
memo.put(key, score);
return score;
}
}