一個pizza切成3n片，每片面積大小不同，每片面積當作一串數列傳入。當你選一片之後，上下兩片會被朋友拿走，請問能拿到的最大面積的為何？
這是一道難題，能解出來的不多。
對於這個 pizza 3n 片這般的難題，除了學會解法之外，更應該去探索解題思路。
暴力解法是很容易，有 3n 片，會有 3n 種取法，3n 種取法後面會衍生出 3n-3 種的取法，如此到底，時間複雜度會是 O(N**N)，所以超過10片就會跑到超時。
不僅運算時間久，衍生出的各種可能也需要保存，空間複雜度也是很大，即便用上 backtrace 降低記憶體使用量，時間複雜度的問題依舊沒有解決。
得用「空間換取時間」，那麼空間要保存甚麼？對，這就是動態規劃的問題。
有沒有甚麼辦法，可以保存各種pizza的拿取情形？參考
若把pizza攤成一排，000000 代表尚未拿取任何一片，100000 代表拿取了第一塊，下一塊不能拿取第一塊鄰近，因此只能選[2]與之後的位置。※注意※Pizza是圓的！
如此類推，只要兩個1不相鄰即可，於是會有 101000、100100、100010、……的拿法，不過這樣還是太多了。
但是繼續往深想，如果拿了第一片，而剩下的組合是固定的，只會出現一種最大取法，不需要分開討論。
於是當前要保存的空間可以推演成 dp[pos][times] ，pos是當前位置，times目前是拿取的次數。
接下來講遞迴函數，經過前面的發想，會是深度優先的dfs，從底搜到頭。
dfs(pos, tiems)，而 dfs(0, 0) 是起點，也代表從0開始取n片的最大值，所以回傳值為當前最大值。
如果還能夠取，就比對 slices[pos] + dfs(pos+2, tiems+1), dfs(pos+1, times)，看誰大取 max()。
如果不能取，當前最大值即 dfs(pos+1, times) 亦作 dfs(pos+1, n) 。
到達最深處，一旦 pos == 3n 或是 times == n，代表無法再取，回傳 0，這要寫在前方。
基本架構完成，問題點來了，前面用※注意※提示Pizza是圓的，萬一同時取到第1片跟最後1片怎麼辦？
當遞回到深處的時候，是無法知道前面是否有取到第一片，那麼最後1片可取或不可取便是疑問。
這有兩個策略，1是分別考慮，從第一片取到第3n-1片與第2片取到第3n片，這裡就不會出現第一片跟最後一片都取到的狀況。2是讓最後一片絕對不取到，甚麼情況下絕對不會取到最後一片，如果最後一片是最小的那塊。
為求簡潔好懂，所以採取2。
class Solution:
def maxSizeSlices(self, slices):
memo = dict()
sl = len(slices)
n = sl//3
minSliceIdx = slices.index(min(slices))
slices = slices[minSliceIdx+1:] + slices[:minSliceIdx+1] # 把最小片的移到最後一塊
def maxSize(pos, times):
if pos >= sl or times == n: return 0
if pos in memo and times in memo[pos]: return memo[pos][times]
else:
if pos not in memo: memo[pos] = {}
if times not in memo[pos]: memo[pos][times] = 0
if times < n:
score = max(slices[pos] + maxSize(pos+2, times+1), maxSize(pos+1, times))
else:
score = maxSize(pos+1, times)
memo[pos][times] = score
return score
return maxSize(0, 0)
做了幾次題目之後，對於DP要建立多維字典實在感到厭倦，如果Python要快速建立多維字典，用 collections.defaultdict 會省下不少時間。
class Solution:
def maxSizeSlices(self, slices):
sl = len(slices)
from collections import defaultdict
memo = defaultdict(dict)
minSliceIdx = slices.index(min(slices))
slices = slices[minSliceIdx+1:] + slices[:minSliceIdx+1] # 把最小片的移到最後一塊
def maxSize(pos, remain):
if pos+remain*2-1 >= sl or remain == 0:
return 0
elif remain in memo[pos]:
return memo[pos][remain]
else:
memo[pos][remain] = max(slices[pos] + maxSize(pos+2, remain-1), maxSize(pos+1, remain))
return memo[pos][remain]
return maxSize(0, sl//3)