Minimum Total Space Wasted With K Resizing Operations LeetCode solution in Java

1
class Solution {
2

3
  // dp[idx][k]=minimum wasted space in between [idx....n-1] if we resize the region k times
4

5
  int INF =
6
      200 * (int) 1e6; // according to constarints { 1 <= nums.length <= 200 , 1 <= nums[i] <= 106 }
7

8
  public int minSpaceWastedKResizing(int[] nums, int k) {
9

10
    int dp[][] = new int[nums.length + 1][k + 1];
11
    memeset(dp, -1);
12
    return f(dp, 0, k, nums);
13
  }
14

15
  int f(int dp[][], int idx, int k, int nums[]) {
16
    if (idx == nums.length) return 0;
17
    if (k == -1) return INF;
18

19
    if (dp[idx][k] != -1) return dp[idx][k];
20

21
    int ans = INF, max = nums[idx], sum = 0;
22

23
    for (int j = idx; j < nums.length; ++j) {
24
      max = Math.max(max, nums[j]);
25
      sum += nums[j];
26
      /**
27
       * total waste in between [idx...j] would be summation of (max-nums[idx] +
28
       * max-nums[idx+1]....max-nums[j]) length would be (j-idx+1) and these summation would be
29
       * (j-idx+1) * max upto j - (nums[idx]+nums[idx+1]....+nums[j]
30
       *
31
       * <p>as i have made one partition in between [idx...j] then remainig (k-1) partitions would
32
       * be in between [j+1....n-1] and that value will be calculated by the recursion and we have
33
       * to take the minimum answer from all these combinations and to avoid tle we are using
34
       * memozization
35
       */
36
      int total_waste_upto_j = (j - idx + 1) * max - sum;
37
      ans = Math.min(ans, total_waste_upto_j + f(dp, j + 1, k - 1, nums));
38
    }
39

40
    return dp[idx][k] = ans;
41
  }
42

43
  void memeset(int dp[][], int val) {
44
    for (int x[] : dp) Arrays.fill(x, val);
45
  }
46
}
47

48
// tc: O(n^2 * k) there will be total (n*k) states  because for each k there are n possibilities and
49
// for each n there will be loop running n times
50
// so in total there will be O(n^2 * k) [because k<n]
51
// sc: O(n*k)