Untitled

 avatar
unknown
java
a year ago
794 B
3
Indexable
    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