Minimum Total Space Wasted With K Resizing Operations LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dp[205][205];
4
#define maxi pow(10, 8)
5
#define ll long long
6
  int dfs(vector<int> &nums, int idx, int k) {
7
    int n = nums.size();
8
    if (idx == n) return 0;
9
    if (k < 0) return maxi;
10
    if (dp[idx][k] != -1) return dp[idx][k];
11
    ll sum = 0, mx = 0, ans = maxi;
12
    for (int i = idx; i < n; i++) {
13
      sum += nums[i];
14
      mx = max(mx, (ll)nums[i]);
15
      ans = min(ans, mx * (i - idx + 1) - sum + dfs(nums, i + 1, k - 1));
16
    }
17
    return dp[idx][k] = ans;
18
  }
19

20
  int minSpaceWastedKResizing(vector<int> &nums, int k) {
21
    memset(dp, -1, sizeof(dp));
22
    return dfs(nums, 0, k);
23
  }
24
};