分冶法將大問題分解成許多類似的小問題，然後再以遞迴的方式分別解決這些小問題，並把他們的解決方案合併起來得到原問題的解決方案。像我們之前學的merge sort和quick sort都是一個分冶法的例子。這裡我們展示分冶法常見的範例，包含入室竊盜問題，變換文字問題， 0 1 背包問題，最長子字串問題，最長回文子字串問題，怎麼走最便宜問題。(翻譯真難，請見下面英文原名比較好理解。)

House Robber problem (入室竊盜問題)

假設你是個小偷，在你要偷的街上有N間房子，然後你知道每間房子裡有價值多少的東西，但你不能偷鄰近的房子，你會怎麼偷(你想偷得最多錢)?

def houseRobber(houses,currentIndex):
    if currentIndex>=len(houses):
        return 0
    else:
        # 如果偷了currentIndex的房子，那就不能偷隔壁的房子(currentIndex+1)
        stealHouse=houses[currentIndex]+houseRobber(houses,currentIndex+2)
        # 如果skip currentIndex的房子，那就看要不要偷隔壁房
        skipHouse=houseRobber(houses,currentIndex+1)
        return max(stealHouse,skipHouse)
    
houses=[6,7,1,30,8,2,4]
print(houseRobber(houses,0))
>> 41
# 他偷了4, 30, 7

Convert String problem (變換文字問題)

給定兩個字串S1和S2，想在最少的步驟裡用刪除、插入、取代這幾個功能讓字串S2變得跟字串S1一樣，要怎麼做?

# 只能用刪除、插入、取代這幾個功能，想讓字串s1和s2一樣
def findMinOperation(s1,s2,index1,index2):
    # 判斷是否已經到s1的底了，這種情況下，剩餘操作次數為len(s2)-index2 (也就是把剩下的s2刪掉)
    if index1==len(s1):
        return len(s2)-index2
    # 同理，判斷是否已經到s2的底，這種情況下，剩餘操作次數len(s1)-index1 (也就是insert字在s2，補齊)
    if index2==len(s2):
        return len(s1)-index1
    # 若字串的字元相等，我們檢查下一個字元
    if s1[index1]==s2[index2]:
        return findMinOperation(s1,s2,index1+1,index2+1)
    # 若字串的字元不相等，我們可以選擇刪除、插入或是取代
    else:
        # 在s2刪除字元，也就是跳過本字元，算是一步，故+1
        deleteOp=1+findMinOperation(s1,s2,index1,index2+1)
        # 在s2插入字元使插入的字元跟s1[index1]一樣，算是一步，故+1，s1要換成看下一個字元
        insertOp=1+findMinOperation(s1,s2,index1+1,index2)
        # 取代變成一樣的字元，算是一步，兩個繼續看下一個index
        replaceOp=1+findMinOperation(s1,s2,index1+1,index2+1)
        return min(deleteOp,insertOp,replaceOp)

print(findMinOperation('apple','cable',0,0))
>> 3

Zero One Knapsack problem (0 1 背包問題)

假定有N個物品，接給定重量與價值，要放進一個重量限制為C的箱子裡，要怎麼放才能使箱子內的物品價值最大?

class Item:
    def __init__(self,value,weight):
        self.weight=weight
        self.value=value

def zoknapsack(item,capacity,currentIndex):
    # set the base condition
    if currentIndex>=len(item):
        return 0
    # 如果可以裝得下current index的item，可以選擇要不要當下這個item
    elif capacity-(item[currentIndex].weight)>=0:
        selectItem=item[currentIndex].value+zoknapsack(item,capacity-item[currentIndex].weight,currentIndex+1)
        skipItem=zoknapsack(item,capacity,currentIndex+1)
        return max(selectItem,skipItem)
    else:
        return 0

A=Item(31,3)
B=Item(26,1)
C=Item(17,2)
D=Item(72,5)
items=[A,B,C,D]
print(zoknapsack(items,9,0))
>> 129

The longest common subsequence problem (最長子字串問題)

給定兩個字串S1和S2，想要在兩字串中找到最長的子字串長度 (S1和S2在透過刪除一些字後能變成的最長子字串)。

def findLCS(s1,s2,index1,index2):
    if index1==len(s1) or index2==len(s2):
        return 0
    elif s1[index1]==s2[index2]:
        return 1+findLCS(s1,s2,index1+1,index2+1)
    else:
        skips2=findLCS(s1,s2,index1,index2+1)
        skips1=findLCS(s1,s2,index1+1,index2)
        return max(skips1,skips2)

print(findLCS('elephant','eretpat',0,0))
>> 5

The longest Palindromic Subsequence problem (最長回文子字串問題)

給定字串S，想找最長的回文子字串長度(palindromic subsequence)。

def LPS(s,start,end):
    if start>end:
        return 0
    # 最後匯集在中間的字惹，算1個字
    elif start==end:
        return 1
    # 有相同字，頭尾共算兩個字，故+2
    elif s[start]==s[end]:
        return 2+LPS(s,start+1,end-1)
    else:
        skipstart=LPS(s,start+1,end)
        skipend=LPS(s,start,end-1)
        return max(skipstart,skipend)
    
print(LPS('ELRMENMET',0,len('ELRMENMET')-1))
>> 5

Minimum cost to reach the last cell problem (怎麼走最便宜問題)

給定一個NxN的二維陣列，陣列中每個位子都有個價錢，我們需要從(0,0)，走到(N-1,N-1)，我們只能向右或向下走，怎麼走能最便宜?

# 從0,0出發，只能向右或向下走, 那用recursion倒過來想，從終點出發，只能向左或向上走
def mincost(array,row,col):
    if row==0 and col==0:
        return array[0][0]
    if row==-1 or col==-1:
        return float('Inf')
    else:
        goup=array[row][col]+mincost(array,row,col-1)
        goleft=array[row][col]+mincost(array,row-1,col)
        return min(goup,goleft)

TwoDList=[[4,7,8,6,4],[6,7,3,9,2],[3,8,1,2,4],[7,1,7,3,7],[2,9,8,9,3]]
print(mincost(TwoDList,4,4))
>> 36

參考資料:
The Complete Data Structures and Algorithms Course in Python (from Udemy)