JZX轻语：简
LeetCode 1444 - 切披萨的方案数
发表于2024年08月24日
一开始想复杂了，以为切后的两片都能再切，其实只能继续切右边/下边的那块(这意味着不用记录剩下的长宽，只要记录下一切的起始点就行，因为能继续切的部分处于原披萨的右下角)，另一块则需要保证有苹果。因此可以使用递归+记忆化搜索解决：记dp(r, c, remain)为从(r, c)开始，剩余remain次切割的方案数：
如果
remain == 0，则只需判断剩下的那块有没有苹果即可，如果有则返回1，否则返回0如果
remain > 0，但是剩下的切数过多，也就是说，即便切成1x1, 还是多余的切数，直接返回0否则，分别考虑横向切和纵向切的情况，如果从某一行/列切下去后，前面的行/列有苹果，则后面的切法都能保证切出来的那块有苹果，此时将
remain减一，从新的起始点递归调用dp函数，累加结果即可。
为了方便判断所切的行/列有没有苹果，以及剩下的最后一块有没有苹果，可以预处理出每一行的最后一个苹果所在列和每一列的最后一个苹果所在行，这样就可以减少循环次数，提高效率。
class Solution:
mod = 10 ** 9 + 7
def ways(self, pizza: List[str], k: int) -> int:
m, n = len(pizza), len(pizza[0])
# 预处理
# 每一行 -> 该行最后一个苹果所在列
# 每一列 -> 该列最后一个苹果所在行
row_to_last = [-1] * m
col_to_last = [-1] * n
for i in range(m):
for j in range(n):
if pizza[i][j] == 'A':
row_to_last[i] = j
col_to_last[j] = i
@lru_cache(None)
def dp(r: int, c: int, remain: int):
if remain == 0:
# 没有剩余的切数
# 看看最后一块有没有苹果
# 不用二重循环, 直接利用预处理的数组进行判断
# 如果剩下的行中, 存在一行最后一个苹果在起始列右边, 就意味着剩下的那块有苹果
for i in range(r, m):
if row_to_last[i] >= c:
return 1
return 0
h, w = m - r, n - c
# 剪枝
# 剩下的切数过多
# 也就是说，即便切成1x1, 还是多余的切数
if remain > (h - 1 + w - 1):
return 0
ans = 0
# == 横向切法 ==
# 当前横切是否有苹果
# 如果切到某一行后, 前面几行已经有苹果, 则后面的切法都会有苹果
has_apple = False
for cut_h in range(1, h):
# 利用预处理结果判断切出来的那块的最后一行是否有苹果
# 当前, 如果前面几行已经有苹果, 则不用判断最后一行了(利用or)
has_apple = has_apple or (row_to_last[r + cut_h - 1] >= c)
if has_apple:
ans = (ans + dp(r + cut_h, c, remain - 1)) % self.mod
# == 纵向切法 ==
# 当前竖切是否有苹果
has_apple = False
for cut_w in range(1, w):
# 同上
has_apple = has_apple or (col_to_last[c + cut_w - 1] >= r)
if has_apple:
ans = (ans + dp(r, c + cut_w, remain - 1)) % self.mod
return ans
return dp(0, 0, k - 1)