給一塊矩陣 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)