Untitled
unknown
c_cpp
a year ago
982 B
8
Indexable
Never
import java.util.*; public class BoxColoring { public static int minimumColorsNeeded(List<Integer> boxes, int s) { int n = boxes.size(); int[] dp = new int[n]; for (int i = 0; i < n; i++) { int min = boxes.get(i), max = boxes.get(i); dp[i] = i + 1; for (int j = i; j >= 0; j--) { min = Math.min(min, boxes.get(j)); max = Math.max(max, boxes.get(j)); if (i - j + 1 > dp[i]) { break; } if (max - min <= s) { dp[i] = Math.min(dp[i], (j > 0 ? dp[j - 1] : 0) + 1); } } } return dp[n - 1]; } public static void main(String[] args) { List<Integer> boxes = new ArrayList<>(Arrays.asList(1, 3, 1, 2, 4, 2, 1)); int s = 2; int result = minimumColorsNeeded(boxes, s); System.out.println(result); // Output: 3 } }