Leetcode題解 Python：Number of Ways of Cutting a Pizza

給一塊矩陣 pizza，要用k-1刀切出 k 塊，每塊上面都要有至少一個 'A'(蘋果)，每刀只能切一直線，而且切完會拿走右方或是上方的那一塊。要回傳有幾種切法。

這算hard中偏簡單的問題，結果我在這題犯小錯卡很久，但正確的主體寫法一下子就寫好了。

因為這題給的拿取規則，使我們隨著每一刀而往右下移動，不用考慮前方的結果。(前不影響後)

因此，使用 dfs(深度優先)，以[y][x]做為dp的依據是沒問題的。(數字很大要取餘也是dp題的特色)

有刀數限制，再組合剛才的dp，組合成 dfs(y, x, pieces)的遞迴函數，而終止條件是 pieces == k。(可能有重複參數出現，可以使用 memo 紀錄)

首先拿到一大塊之後，可以直切，也可以橫切，選一個間隔作為下刀點。此時可分左右或上下。

如果被取走的那塊有蘋果，就可以往下一刀進行。dfs(y1, x1, pieces+1)

所以，總要判斷給定的區間內pizza是否有 1 個 "A"，寫成一個函數。(可能有重複參數出現，可以使用 memo 紀錄)

dfs 來到當 pieces == k ，就以目前的範圍找是否有蘋果，有則回傳 1 ，沒有則 0。

Python

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
	from functools import lru_cache
        rows, cols = len(pizza), len(pizza[0])         
        @lru_cache(None)
        def hasApple(y0,y1,x0,x1):
            for y in range(y0,y1): 
                for x in range(x0,x1):        
                    if pizza[y][x] == "A": return True
            return False        
        @lru_cache(None)
        def dfs(y, x, pieces):
            if pieces == k:                
                if hasApple(y,rows, x,cols): 
                    return 1 
                else: return 0
                
            ans = 0
            # h cut
            for i in range(y, rows-1):                
                if hasApple(y, i+1, x, cols): 
                    ans += dfs(i+1, x, pieces+1)
            # v cut
            for i in range(x, cols-1):
                if hasApple(y, rows, x, i+1): 
                    ans += dfs(y, i+1, pieces+1)  
            return ans % (10**9+7)
        return dfs(0, 0, 1)