1959. Minimum Total Space Wasted With K Resizing Operations

• Time: $O(n^2k)$
• Space: $O(nk)$

C++JavaPython

class Solution {
 public:
  int minSpaceWastedKResizing(vector<int>& nums, int k) {
    vector<vector<int>> mem(nums.size(), vector<int>(k + 1, -1));
    return minSpaceWasted(nums, 0, k, mem);
  }

 private:
  static constexpr int kMax = 200'000'000;

  // Returns the minimum space wasted for nums[i..n) if you can resize k times.
  int minSpaceWasted(const vector<int>& nums, int i, int k,
                     vector<vector<int>>& mem) {
    if (i == nums.size())
      return 0;
    if (k == -1)
      return kMax;
    if (mem[i][k] != -1)
      return mem[i][k];

    int res = 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;
      res = min(res, minSpaceWasted(nums, j + 1, k - 1, mem) + wasted);
    }

    return mem[i][k] = res;
  }
};

class Solution {
  public int minSpaceWastedKResizing(int[] nums, int k) {
    Integer[][] mem = new Integer[nums.length][k + 1];
    return minSpaceWasted(nums, 0, k, mem);
  }

  private static final int MAX = 200_000_000;

  // Returns the minimum space wasted for nums[i..n) if you can resize k times.
  private int minSpaceWasted(int[] nums, int i, int k, Integer[][] mem) {
    if (i == nums.length)
      return 0;
    if (k == -1)
      return MAX;
    if (mem[i][k] != null)
      return mem[i][k];

    int res = MAX;
    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;
      res = Math.min(res, minSpaceWasted(nums, j + 1, k - 1, mem) + wasted);
    }

    return mem[i][k] = res;
  }
}

class Solution:
  def minSpaceWastedKResizing(self, nums: list[int], k: int) -> int:
    MAX = 200_000_000

    @functools.lru_cache(None)
    def dp(i: int, k: int) -> int:
      """
      Returns the minimum space wasted for nums[i..n) if you can resize k times.
      """
      if i == len(nums):
        return 0
      if k == -1:
        return MAX

      res = MAX
      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
        res = min(res, dp(j + 1, k - 1) + wasted)

      return res

    return dp(0, k)