主題
題目連結：
題目意譯：
給定兩個整數陣列 arr1 和 arr2，回傳最少所需的操作數（可能為零次）來使得 arr1 嚴格遞增。
在一次操作中，你可以選擇兩個索引值0 ≦ i < arr1.length 和 0 ≦ j < arr2.length 來使 arr1[i] 變成 arr2[j]。
如果不可能使 arr1 變成嚴格遞增，則回傳 -1。
限制：
1 ≦ arr1.length, arr2.length ≦ 2000
0 ≦ arr1[i], arr2[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
輸出： 1
解釋： 將 5 替換成 2，則 arr1 = [1, 2, 3, 6, 7]。
範例 2：
輸入： arr1 = [1,5,3,6,7], arr2 = [4,3,1]
輸出： 2
解釋： 將 5 替換成 3 並將 3 替換成 4。arr1 = [1, 3, 4, 6, 7]。
範例 3：
輸入： arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
輸出： -1
解釋： 你無法將 arr1 變成嚴格遞增。
解題思維：
假設現在我們看到的是 arr1[i]。而同時，我們也知道先前 arr1[i - 1] 可能會變成哪些數字並且已知其每一種數字所需最少操作數。則 arr1[i] 可以是哪些數字？
如果現在 arr1[i - 1] 會變成某一種數字 P，且其最少所需操作次數為 t 次。則此時如果 P < arr1[i]，則我們可以維持不變（注意，這是對於 P 來說；這種 P 值可能很多個）。因此次數為 t。
接著，不管前面的結果為何，我們可以藉由二分搜尋法（Binary Search）來在 arr2 中找到第一個大過 P 的數字，稱其為 P'（記得要先將 arr2 排序才能二分搜），並將 arr1[i] 變成 P'（可能會可以讓後面的數字方便接續，也可能不會）。因此次數為 t + 1。
因此定義一個函式 D，其中 D(i, j) 為 arr1[i] 要變成 j 的最少所需操作數。（這次寫「函式」而不是陣列是因為某一個維度是 0 ～ 10 ^ 9 的「稀疏」數字們，所以直接用陣列存會爆炸。可以改用雜湊表（Hash Table）等資料結構）。
根據前面的觀察，可以看到遞迴式為：
D(0, arr1[0]) = 0；
D(0, j) = 1，其中 j != arr1[0] 且 j 存在於 arr2 之中。
（上面兩式為遞迴的停止條件）
D(i, i) = min(D(i - 1, P))，其中 P < arr1[i]（注意 P 值可能很多個，所以 min() 裡面的是「集合」）。
D(i, j) = min(D(i - 1, P) + 1)，其中 j 是 P 在 arr2 從小數字掃到大數字的情況下，第一個大過 P 的數字。
不過這次不能直接遞迴（本人認為會很麻煩，如果我是錯的請指正）。所以我們要從 D(0, arr[0]) 以及 D(0, j) 開始推算。
推出所有可能的 D(0, j) 之後，就用這些資料往 D(1, j) 推算；算完了就往 D(2, j) 算……以此類推。
最後的所求即為所有可能的 D(arr1.length - 1, j) 中的最小值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
