給出一個由.和A組成的二維矩陣，A表示該個點有apple。每次可以橫切或豎切，問切k-1刀將矩陣分為k塊有多少種方式（每塊至少包含一個A）
完全沒想出如何記錄狀態，參考了Discussion：https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/solutions/3360818/easy-solutions-in-java-python-and-c-look-at-once-with-exaplanation
1 #1444
2 #Runtime: 203 ms (Beats 68%)
3 #Memory: 14.1 MB (Beats 74%)
4
5 class Solution(object):
6 def ways(self, pizza, k):
7 """
8 :type pizza: List[str]
9 :type k: int
10 :rtype: int
11 """
12 m = len(pizza)
13 n = len(pizza[0])
14 dp = [[[None] * n for _ in range(m)] for _ in range(k)]
15 preSum = [[0] * (n+1) for _ in range(m + 1)]
16 for r in range(m - 1, -1, -1):
17 for c in range(n - 1, -1, -1):
18 preSum[r][c] = preSum[r+1][c] + preSum[r][c+1] - preSum[r+1][c+1] + (pizza[r][c] == 'A')
19
20 def DFS(m, n, k, r, c, dp):
21 if preSum[r][c] == 0:
22 return 0
23 if k == 0:
24 return 1
25 if dp[k][r][c] is not None:
26 return dp[k][r][c]
27 ans = 0
28 for nr in range(r + 1, m):
29 if preSum[r][c] - preSum[nr][c] > 0:
30 ans = (ans + DFS(m, n, k - 1, nr, c, dp)) % 1000000007
31 for nc in range(c+1, n):
32 if preSum[r][c] - preSum[r][nc] > 0:
33 ans = (ans + DFS(m, n, k - 1, r, nc, dp)) % 1000000007
34 dp[k][r][c] = ans
35 return ans
36
37 return DFS(m, n, k - 1, 0, 0, dp)