Skip to content

1959. Minimum Total Space Wasted With K Resizing Operations 👍

  • Time: $O(n^2k)$
  • Space: $O(nk)$
 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
31
32
33
34
class Solution {
 public:
  int minSpaceWastedKResizing(vector<int>& nums, int k) {
    // dp[i][k] := min space wasted for nums[i:] if you can resize k times
    dp.resize(nums.size(), vector<int>(k + 1, -1));
    return minSpaceWasted(nums, 0, k);
  }

 private:
  static constexpr int kMax = 200'000'000;
  vector<vector<int>> dp;

  int minSpaceWasted(const vector<int>& nums, int i, int k) {
    if (i == nums.size())
      return 0;
    if (k == -1)
      return kMax;
    if (dp[i][k] != -1)
      return dp[i][k];

    int ans = kMax;
    int sum = 0;
    int maxNum = nums[i];

    for (int j = i; j < nums.size(); ++j) {
      sum += nums[j];
      maxNum = max(maxNum, nums[j]);
      const int wasted = maxNum * (j - i + 1) - sum;
      ans = min(ans, minSpaceWasted(nums, j + 1, k - 1) + wasted);
    }

    return dp[i][k] = ans;
  }
};

 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
31
32
class Solution {
  public int minSpaceWastedKResizing(int[] nums, int k) {
    // dp[i][k] := min space wasted for nums[i:] if you can resize k times
    dp = new Integer[nums.length][k + 1];
    return minSpaceWasted(nums, 0, k);
  }

  private static final int kMax = 200_000_000;
  private Integer[][] dp;

  private int minSpaceWasted(int[] nums, int i, int k) {
    if (i == nums.length)
      return 0;
    if (k == -1)
      return kMax;
    if (dp[i][k] != null)
      return dp[i][k];

    int ans = kMax;
    int sum = 0;
    int maxNum = nums[i];

    for (int j = i; j < nums.length; ++j) {
      sum += nums[j];
      maxNum = Math.max(maxNum, nums[j]);
      final int wasted = maxNum * (j - i + 1) - sum;
      ans = Math.min(ans, minSpaceWasted(nums, j + 1, k - 1) + wasted);
    }

    return dp[i][k] = ans;
  }
}

 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
class Solution:
  def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
    kMax = 200_000_000

    # dp(i, k) := min space wasted for nums[i:] if you can resize k times
    @functools.lru_cache(None)
    def dp(i: int, k: int) -> int:
      if i == len(nums):
        return 0
      if k == -1:
        return kMax

      ans = kMax
      summ = 0
      maxNum = nums[i]

      for j in range(i, len(nums)):
        summ += nums[j]
        maxNum = max(maxNum, nums[j])
        wasted = maxNum * (j - i + 1) - summ
        ans = min(ans, dp(j + 1, k - 1) + wasted)

      return ans

    return dp(0, k)