C++刷LeetCode（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.length
1 <= k <= 10
pizza 只包含字符 'A' 和 '.' 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
int mode = 1e9+7;
vector<vector<int> >number;
public:
//计算以i, j为左上角顶点;m,n为右下角顶点的矩形中是否有A
bool Has_A(int i, int j, int m, int n){
int temp1 = 0, temp2 = 0, temp3 = 0;
if(i-1 >= 0)temp1 = number;
if(j-1 >= 0)temp2 = number;
if(i-1 >= 0 && j-1 >= 0)temp3 = number;
return number - (temp1 + temp2 - temp3) > 0;
}
int ways(vector<string>& pizza, int k) {
int len1 = pizza.size(), len2 = pizza.size();
//number记录以(i,j)为底的pizza中有多少个苹果
number = vector<vector<int> >(len1, vector<int>(len2, 0));
if(pizza == 'A')number = 1;
for(int i = 1; i < len1; i++){
number = number + (pizza == 'A');
}
for(int j = 1; j < len2; j++){
number = number + (pizza == 'A');
}
for(int i = 1; i < len1; i++){
for(int j = 1; j < len2; j++){
number = number + number - number + (pizza == 'A');
}
}
//dpi,j表示披萨剩余部分的左上角,k表示当前披萨被切成k块
vector<vector<vector<int> > >dp(len1, vector<vector<int> >(len2, vector<int>(k+1, 0)));
//初始化
dp = 1;
for(int m = 2; m <= k; m++){
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
if(dp == 0)continue;
//穷举水平切
for(int z = i+1; z < len1; z++){
if(Has_A(i, j, z-1, len2-1) && Has_A(z, j, len1-1, len2-1)){
dp += dp;
dp %= mode;
}
}
//穷举垂直切
for(int z = j + 1; z < len2; z++){
if(Has_A(i, j, len1-1, z - 1) && Has_A(i, z, len1-1, len2-1)){
dp += dp;
dp %= mode;
}
}
}
}
}
long long res = 0;
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
res += dp;
}
res %= mode;
}
return res;
}
};
参考链接：https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza/solution/dong-tai-gui-hua-c-by-smilyt_/
页:
[1]