Untitled
public static int calculateCost(List<Integer> arr, int threshold) { if (threshold >= arr.size()) { return Collections.max(arr); } int[] dp = new int[arr.size()]; Arrays.fill(dp, Integer.MAX_VALUE); for (int i = 0; i < threshold; i++) { dp[i] = arr.get(i); } for (int i = threshold; i < arr.size(); i++) { int dpi = Integer.MAX_VALUE; for (int j = i - threshold; j < i; j++) { int mval = Integer.MIN_VALUE; for (int k = j + 1; k <= i; k++) { mval = Math.max(mval, arr.get(k)); } dpi = Math.min(dpi, dp[j] + mval); } dp[i] = dpi; } return dp[arr.size() - 1]; }
Leave a Comment