一、原始想法
（一）概念
 |
| 原始概念圖 |
題意為給兩個序列A和B，只能交換同行的AB元素，使得A和B為嚴格遞增序列(A[1]<A[2]...)的最小交換次數。如果A[i-1] < B[i] < A[i+1]且B[i-1] < A[i] < B[i+1]為真，則swap(A[i], B[i])是安全的，因為不會增加更多遞減。
（二）實作
 |
| isSafe() 程式碼 |
isSafe()可以拿來檢查swap(A[i], B[i])是否安全？
 |
| 主架構 程式碼 |
只檢查i是否安全是不夠的，因為有可能i-1也是安全的，因此為了要消掉遞增，我們至少就有2種選擇，因此我們需要知道翻轉i-1比較好？還是翻轉i比較好？主架構考慮了4種情境：
- pair(i-1, i)和pair(i, i+1)都是遞減的，且i是安全的，翻轉i是比較好的選擇，因為翻轉i可以消掉2個遞增。即使i-1也是安全的，但翻轉i-1只能消掉1個遞減。
- i-1是安全的，優先翻轉i-1。
- i-1是不安全，但i是安全的，則翻轉i。
- i-1和i都是不安全的，則向左向右，搜尋連續不安全的邊界，然後執行最大連續不安全數較少的一方。
最後我的演算法在98 / 117是失敗，顯然我沒有考慮到所有情境。我覺得我沒有處理到連續遞減的情境，這可能是需要再思考的。
二、動態規劃 (Dynamic programming)
（一）概念
 |
| 動態規劃 概念 |
上圖左邊為動態規劃的遞迴關係式，這裡使用了兩張表格，分別為swap和notSwap，一開始初始化為別為1和0。遞迴關係式有兩條，會先執行第1條，再執行第2條。
- 如果A[i-1] < A[i]且B[i-1] < B[i]，則swap[i] = swap[i-1]+1，意思為我翻轉i-1且翻轉i；notSwap[i] = notSwap[i-1]，意思為我不翻轉i-1且不翻轉i
- 如果A[i-1] < B[i]且B[i-1] < A[i]，則swap[i] = min(swap[i], notSwap[i-1]+1)，意思為我不翻轉i-1但翻轉i；notSwap[i] = min (swap[i-1], notSwap[i])，意思為我翻轉i-1但不翻轉i。
swap[n] means the minimum swaps to make the A[i] and B[i] sequences increasing for 0 <= i <= n, in condition that we swap A[n] and B[n] notSwap[n] is the same with A[n] and B[n] not swapped.
（二）實作
 |
| 動態規劃 程式碼 |
三、相關文章
請詳見LeetCode相關文章
留言
張貼留言