1444. 切披萨的方案数
给你一个 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' 和 '.' 。
思路：首先二维前缀和预处理出特定二维区域的含披萨个数，nums[i][j]表示左上角坐标是i,j到n-1,m-1区域所包含的披萨数
接着考虑dp[i][j][k]:表示左上角坐标是i,j到n-1,m-1区域切成k块的方案数，要么横着切，要么竖着切，
先预处理dp[i][j][1]只要区域里面有披萨就ok
单说一种情况就好：
横着切就是切i 1行之后的，暴力枚举q，只要判断nums[i][j]-nums[q][j]>=1即可，q>i,q<n加上这种方案就好,
代码语言：javascript复制class Solution {
public:
const int mod=1e9 7;
int ways(vector<string>& pizza, int k) {
int n=pizza.size(),m=pizza[0].size();
int nums[55][55]={0};
for(int i=n-1;i>=0;i--)
{
for(int j=m-1;j>=0;j--)
{
nums[i][j] =nums[i 1][j] nums[i][j 1]-nums[i 1][j 1] (pizza[i][j]=='A');
}
}//前缀和初始化
int dp[55][55][15]={0};
for(int i=0;i<n;i )
{
for(int j=0;j<m;j )
{
if(nums[i][j])dp[i][j][1]=1;
}
}
for(int i=n-1;i>=0;i--)
{
for(int j=m-1;j>=0;j--)
{
for(int h=2;h<=k;h )
{
for(int q=i 1;q<n;q )
{
if(nums[i][j]-nums[q][j]>=1)
{
dp[i][j][h] =dp[q][j][h-1];
dp[i][j][h]%=mod;
}
}
for(int q=j 1;q<m;q )
{
if(nums[i][j]-nums[i][q]>=1)
{
dp[i][j][h] =dp[i][q][h-1];
dp[i][j][h]%=mod;
}
}
//cout<<dp[i][j][h]<<" ";
}
//cout<<endl;
}
}
return dp[0][0][k];
}
};
