主題
題目連結：
題目意譯：
給定一個矩形狀的披薩，其以一個大小為 rows × cols 的矩陣所表示，其矩陣包含以下字元：'A'（一顆蘋果）和 '.'（空格）。同時你也被給定一整數 k。你需要對披薩切 k - 1 刀來將它分成 k 塊。
對於每一刀，你將先選擇方向：垂直或是水平；接著你將選擇位於格子邊界作為下刀的位置並接著將披薩切成兩塊。如果你是垂直地縱切披薩，則把切完後左邊的部分給某個人；而如果你是水平地橫切披薩，則把切完後上面的部分給某個人。而最後一塊披薩則給最後一個人。
回傳所有可能的披薩切割方法數，使得切法中每一塊至少包含一顆蘋果。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
限制：
1 ≦ rows, cols ≦ 50
rows == pizza.length
cols == pizza[i].length
1 ≦ k ≦ 10
pizza 只由字元 'A' 和 '.' 所組成。
範例測資：
範例 1：
輸入： pizza = ["A..","AAA","..."], k = 3
輸出： 3
解釋： 上圖顯示了三種切披薩的方式。注意到每一塊之中必須包含至少一顆蘋果。
範例 2：
輸入： pizza = ["A..","AA.","..."], k = 3
輸出： 1
範例 3：
輸入： pizza = ["A..","A..","..."], k = 1
輸出： 1
解題思維：
首先先利用這題的想法建立出二維前綴和（Prefix Sums），讓我們可以在常數時間內得到矩陣 pizza 中任一個子矩陣內的蘋果數量。
接下來就是經典的動態規劃（Dynamic Programming，DP）之題型：
定義一個三維矩陣 D，其中 D[r][c][x] 代表著以矩陣 pizz 中以左上角 (r, c) 且右下角 (rows - 1, cols - 1) 的這個子矩陣來說，在需要切 x 刀的情況下，符合題目的切法之方法數。
因此我們可以看到其遞迴式為：
如果 D[r][c][x] 代表著子矩陣中沒有蘋果（利用一開始建立的前綴和來算），則 D[r][c][x] = 0；
如果 x 為 0，則代表只有現在「一種切法」，即維持原狀，因此 D[r][c][x] = 1；
如果 r 為 rows - 1 、 c 為 cols - 1 且 x 不為 0，則代表剩下沒辦法再切了，因此 D[r][c][x] = 0；
如果以上皆非，則 D[r][c][x] = D[i + 1][c][x - 1] + D[r][j + 1][x - 1]，對於所有滿足 r ≦ i < rows - 1 的 i 值且左上角 (r, c) 而右下角為 (i, cols - 1) 的子矩陣要有蘋果；以及所有滿足 c ≦ j < cols - 1 的 j 值且左上角 (r, c) 而右下角為 (rows - 1, j) 的子矩陣要有蘋果。
因此我們利用深度優先搜尋（Depth First Search，DFS）的精神 + 記錄已經求過的答案去遞迴求得 D[0][0][k - 1] 之值，最後便可以得到所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
