2919. Minimum Increment Operations to Make Array
DFS+memo
```java
class Solution {
public long minIncrementOperations(int[] nums, int k) {
Long[] memo = new Long[nums.length];
return dfs(0, nums, k, memo);
}
private long dfs(int i, int[] nums, int k, Long[] memo) {
int n = nums.length;
if (i > n - 3) { //base case: not in subarray win -> return 0
return 0;
}
if (memo[i] != null) {
return memo[i];
}
// try to brute force DFS to get all values...but with memo -> DP
// option 1, how many ops at for reaching k, (k - current num)
// k - nums might < 0, ex: [1,1,2], k=1, this case, k - nums[i + 2] is -1
// so it means no operations! => use 0
long op1 = Math.max(0, k - nums[i]) + dfs(i + 1, nums, k, memo);
// option 2
long op2 = Math.max(0, k - nums[i + 1]) + dfs(i + 2, nums, k, memo);
// option 3
long op3 = Math.max(0, k - nums[i + 2]) + dfs(i + 3, nums, k, memo);
return memo[i] = Math.min(op1, Math.min(op2, op3));
}
}
/**
>=3
maxi >= k
result =
current index is i
op1 = max(0, k - num[i]) + dfs(i+1, ...)
or
op1 = max(0, k - num[i+1]) + dfs(i+2, ...)
or
op1 = max(0, k - num[i+2]) + dfs(i+3, ...)
MIN(op1, op2, op3)
*/
```
DP
```java
class Solution {
public long minIncrementOperations(int[] nums, int k) {
int n = nums.length;
long res = Long.MAX_VALUE;
long[] dp = new long[n];
dp[0] = Math.max(0, k - nums[0]);
dp[1] = Math.max(0, k - nums[1]);
dp[2] = Math.max(0, k - nums[2]);
for (int i = 3; i < n; i++) {
dp[i] = Math.max(0, k - nums[i]) + Math.min(Math.min(dp[i - 3], dp[i - 2]), dp[i - 1]);
}
//System.out.println(Arrays.toString(dp));
return Math.min(Math.min(dp[n - 3], dp[n - 2]), dp[n - 1]);
}
}
/**
2, 3 0,0,2
2 1 4
5 3
for idx = 4, nums = 0
k-0 = 4
min[2,1,4] -> 1
so 4+1 = 5
so until idx 4, dp[4] = 5 -> [2, 3, 0, 0] -> [2,4, 0 ,4] -> so [2,4,0], [4,0,4] ->
we have op 5 times to make all win >= 3 can reach 4
but for idx = 5, nums=2
k-2 = 2 +
min [1 4 5] -> is 1
2+1 = 3
you can see in [3,0,0, 2] -> we make it to [4,0,0,4] -> 3 ops
-> because idx5 nums = 2 -> so we can only use ops 3 to make all range to idx 5 reach to 4
result dp = [2, 1, 4, 5, 3]
at last only to find min in last 3 values (it's a result)
*/
```
Last updated