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)
 */
```