作孽呀，劝退一个月薪35K，有房贷车贷有俩娃的40岁中年研发~

简单说就是，给你一张披萨，上面有些格子有料，有些没料。要求你用最多k刀，把披萨切成k块，每一块都必须有料。问有多少种切法？其实就是分割一个二维的矩阵，然后每块都得保证带料，你们说这是不是很像我们工作分任务，不能有的组摸鱼没活干。

我一开始直接想暴力搜，递归+暴力枚举切法，切一刀横切一刀竖切，这样一路枚举下去，但是人傻了，直接超时。纸上画了半天才发现，诶这不是典型的“带记忆化的搜索”嘛，你搜的时候很多重复子问题都可以记下来，不然你递归到后面全都是重复算一遍。

我那天是先用二维前缀和预处理了一下，哪个子披萨区间是有料的，这样判定一块披萨是不是有料就O(1)了。然后主流程就是个dfs，参数是当前左上角(x, y)，还剩几刀要切。

比如你当前位置(x, y)，还剩rest刀，那你可以往下枚举横切（比如在row+1 ~ n-1之间切），只要保证切下去的那块有料，然后剩下的递归处理，竖切也一样。

记忆化就直接用个三维数组dp[x][y][rest]存结果，每次算出来直接存，不用重新算。

大概就像这样（我就直接写py了，写Java手快慢手慢打）：

MOD = 10**9 + 7

defways(pizza, k):
    m, n = len(pizza), len(pizza[0])
# 预处理前缀和
    pre = [[0]*(n+1) for _ in range(m+1)]
for i in reversed(range(m)):
for j in reversed(range(n)):
            pre[i][j] = (1if pizza[i][j]=='A'else0) + pre[i+1][j] + pre[i][j+1] - pre[i+1][j+1]

from functools import lru_cache
    @lru_cache(maxsize=None)
defdfs(x, y, rest):
# 没料直接return 0
if pre[x][y] == 0:
return0
# 剩一块，不用切了，只要有料就是1种
if rest == 1:
return1
        res = 0
# 横切
for i in range(x+1, m):
if pre[x][y] - pre[i][y] > 0:
                res = (res + dfs(i, y, rest-1)) % MOD
# 竖切
for j in range(y+1, n):
if pre[x][y] - pre[x][j] > 0:
                res = (res + dfs(x, j, rest-1)) % MOD
return res

return dfs(0, 0, k)

这思路其实就跟那种小区切蛋糕的感觉，切一刀看看分出来那一半有没有料，有就继续递归。不行就不切这刀。就是写递归的时候别忘了边界条件，不然人都得疯。横竖都可以切，记得判断剩下的那块必须得有料。

你们别觉得算法高大上，其实就像部门KPI分配，一定得每个人头上都有点活，不能全交给老李一个人，剩下全是划水的。不然老板一拍桌子，你怎么分的活？这披萨题不就是这样么——每块都要有内容。

而且说真的，写这种题最容易卡的是记忆化，你不写cache递归直接爆炸，分分钟TLE。你得记住：子问题重复就要dp，状态维度要抓准（这题就是位置和剩余刀数）。

写完其实一看，就是典型的递归+dp剪枝，思路很套路，但遇到变形就容易懵，所以我都是边画边写，画了半天饭都凉了。

切完披萨那天我记得我还拍了张照片，发到群里，说"这题终于懂了，顺便自制披萨，懂的都懂"。大家都开始讨论那种披萨最好吃，直接从算法题聊到深夜外卖推荐……有时候真服了，程序员生活一半技术一半美食。