本题是力扣188期周赛中的最后一题。
一、题目
给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。
切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。
示例 1：
输入：pizza = ["A..","AAA","..."], k = 3
输出：3
解释：上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。
示例 2：
输入：pizza = ["A..","AA.","..."], k = 3
输出：1
示例 3：
输入：pizza = ["A..","A..","..."], k = 1
输出：1
提示：
- 1 <= rows, cols <= 50, rows == pizza.length, cols == pizza[i].length
- 1 <= k <= 10
- pizza 只包含字符 'A' 和 '.' 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza
二、题解（动态规划）
题目简化下来其实就是矩阵切割k-1次切割为k份，每一刀切掉切口上方或者左方一块，要求每一块里必须包含A，求切法总数。
看完题目基本就知道是动态规划类型的题，要不断地从普通状态转换到最简单的状态。一个矩阵可以从不同的行或列切为2份，但是这一刀切下去需要保证两个前提：
- 切割出来的左边或者上边部分包含A
- 剩余的部分包含A的数量不少于k-1, 因为还要将剩下部分分割给k-1个人。
总的切割方法数量即当前任意切法切割后剩余部分分割给k-1个人的方法数量总和。
这样就将k个人的分割方法计算转换为了k-1个人的分割方法数。直到剩余的A数量比剩余人数少，或者仅剩余1个人，此时就是最简单的状态，可以直接知道余下部分的切割方法。
Javascript代码实现：
var ways = function(pizza, k) {
let count = 0
for (let row of pizza) {
for (let i = 0; i < row.length; i++) {
row[i] == 'A' && count++
}
}
return cal(pizza, k, count)
};
function cal (pizza, k, countA, record = {}) {
if (!pizza.length) return 0
let rows = pizza.length, cols = pizza[0].length
let recordKey = `${rows}-${cols}-${k}`
if (recordKey in record) return record[recordKey]
if (k > countA) {
record[recordKey] = 0
} else if (k <= 1) {
record[recordKey] = 1
} else {
record[recordKey] = 0
let cutA = 0, rest = [...pizza]
// 计算从各个位置横切的切法
while (rest.length > 1) {
const cut = rest.shift()
for (let i = 0; i < cut.length; i++) if (cut[i] == 'A') cutA++
// 如果上方没有A，这个切割不合要求，直接跳过
if (!cutA) continue
record[recordKey] += cal(rest, k - 1, countA - cutA, record)
}
//计算竖切
cutA = 0
for (let i = 0; i < pizza[0].length - 1; i++) {
for (let j = 0; j < pizza.length; j++) if (pizza[j][i] == 'A') cutA++
if (!cutA) continue
rest = pizza.map(s => s.slice(i + 1))
record[recordKey] += cal(rest, k - 1, countA - cutA, record)
}
}
record[recordKey] = record[recordKey] % (Math.pow(10, 9) + 7)
return record[recordKey]上述代码中使用了record对象记录已经计算过的右下角rows行cols列分割给k人的分割方法数，以避免递归过程中的重复计算。