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)