1444. Number of Ways of Cutting a Pizza
你有一塊矩形的披薩，上面有一些蘋果，有 k 個小朋友等著吃披薩
你每次都要切下一塊上面有蘋果的披薩交給小朋友，求切法總數 mod 10^9+7
*切法限制水平切或垂直切，水平切交出上半部分，垂直切交出左半部分
Example 1:
https://assets.leetcode.com/uploads/2020/04/23/ways_to_cut_apple_1.png
Input: pizza = ["A..","AAA","..."], k = 3
Output: 3
切法如圖
Example 2:
Input: pizza = ["A..","AA.","..."], k = 3
Output: 1
Example 3:
Input: pizza = ["A..","A..","..."], k = 1
Output: 1
思路:
1.切完一刀之後其實就是 k -= 1 後範圍縮小 然後原問題再解一次 馬上想到用dp
假設 dp[0, 0, k] 代表目前的披薩左上角是 (0, 0) 且要分給 k 個小朋友
切法就能寫成 dp[0, 0, k] += dp[i, 0, k-1] for i in range(0~len(pizza)) #水平切
dp[0, 0, k] += dp[0, j, k-1] for j in range(0~len(pizza[0])) #垂直切
像這樣
@cache
def dp(x, y, cut):
if cut == 0:
return 1
res = 0
for i in range(x+1, m):
res += dp(i, y, cut-1)
for i in range(y, n):
res += dp(x, i, cut-1)
return res%mod
2.因為要保證切下的部分必須至少有一塊蘋果 可以用 prefix sum 的概念先建表
apple[i][j] 代表 (i, j) 右下部分的蘋果總數
這樣就能快速算出切這刀有沒有切出蘋果
用上面當例子 水平切就是檢查 apple[0][0] - apple[i][0] 有沒有大於零
垂直切就是檢查 apple[0][0] - apple[0][j]
3.可以順便檢查 apple[i][j] 有沒有比現在的 k 多來剪枝 沒有就直接失敗
Python code:
class Solution:
def ways(self, pizza: List[str], k: int) -> int:
m, n = len(pizza), len(pizza[0])
mod = 10**9+7
apple = [[0]*(n+1) for _ in range(m+1)]
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
apple[i][j] = (pizza[i][j] == 'A') + apple[i][j+1] +
apple[i+1][j] - apple[i+1][j+1]
@cache
def dp(x, y, cut):
if cut == 0:
return 1
res = 0
for i in range(x+1, m):
if apple[x][y] - apple[i][y] > 0 and apple[i][y] >= cut:
res += dp(i, y, cut-1)
for i in range(y, n):
if apple[x][y] - apple[x][i] > 0 and apple[x][i] >= cut:
res += dp(x, i, cut-1)
return res%mod
return dp(0, 0, k-1)