# LC 1187. Make Array Strictly Increasing

### [Problem link](https://leetcode.com/problems/make-array-strictly-increasing/)

###### tags: `leedcode` `python` `hard` `DP`

Given two integer arrays<code>arr1</code> and <code>arr2</code>, return the minimum number of operations (possibly zero) neededto make <code>arr1</code> strictly increasing.

In one operation, you can choose two indices<code>0 <=i < arr1.length</code>and<code>0 <= j < arr2.length</code>and do the assignment<code>arr1[i] = arr2[j]</code>.

If there is no way to make<code>arr1</code>strictly increasing,return<code>-1</code>.

**Example 1:**

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace <code>5</code> with <code>2</code>, then <code>arr1 = [1, 2, 3, 6, 7]</code>.

**Example 2:**

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace <code>5</code> with <code>3</code> and then replace <code>3</code> with <code>4</code>. <code>arr1 = [1, 3, 4, 6, 7]</code>.

**Example 3:**

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make <code>arr1</code> strictly increasing.

**Constraints:**

- <code>1 <= arr1.length, arr2.length <= 2000</code>
- <code>0 <= arr1[i], arr2[i] <= 10^9</code>

## Solution 1 - DP

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        dp = {}
        arr2.sort()

        def dfs(i, prev):
            '''
            i: The current position of arr1.
            prev: The value of arr1[i - 1].
            '''
            if i == len(arr1):
                return 0
            if (i, prev) in dp:
                return dp[(i, prev)]

            # type 2
            cost = float('inf')
            if arr1[i] > prev:
                cost = dfs(i + 1, arr1[i])

            # type 1, 3
            idx = bisect.bisect_right(arr2, prev)
            if idx < len(arr2):
                cost = min(cost, 1 + dfs(i + 1, arr2[idx]))

            dp[(i, prev)] = cost
            return cost

        res = dfs(0, -1)

        return res if res < float('inf') else -1

>### Complexity
>m = arr1.length
>n = arr2.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mnlogn) | O(mn) |

## Note
從上到下共有三種可能要討論, 其中第一種與第三種都需要binary search, 可以看成同一種,所以

total cost = min(cost, 1 + dfs(i + 1, arr2[idx]))
總cost = min(第二種cost, 第一三種cost + 1)

TC:
sort arr2: nlogn
dfs: i 有m + 1種可能, prev有n + 1種可能, 每對(i, prev)都可能要對arr2做一次binary search
所以TC = O(nlogn + mnlogn) = O(mnlogn)

[Leetcode官方解答](https://leetcode.com/problems/make-array-strictly-increasing/editorial/)
[官神github](https://github.com/wisdompeak/LeetCode/blob/master/Dynamic_Programming/1187.Make-Array-Strictly-Increasing/1187.Make-Array-Strictly-Increasing.cpp)