山东兴华建设集团有限公司网站,免费做网站的app,有什么网站是做办公家具,wordpress更改网站内容目录
1444. 切披萨的方案数
题目描述#xff1a;
实现代码与解析#xff1a;
二维后缀和 动态规划
原理思路#xff1a; 1444. 切披萨的方案数
题目描述#xff1a; 给你一个 rows x cols 大小的矩形披萨和一个整数 k #xff0c;矩形包含两种字符#xff1a; A …目录
1444. 切披萨的方案数
题目描述
实现代码与解析
二维后缀和 动态规划
原理思路 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 50rows pizza.lengthcols pizza[i].length1 k 10pizza 只包含字符 A 和 . 。
实现代码与解析
二维后缀和 动态规划
class Solution {
public:int ways(vectorstring pizza, int k) {int m pizza.size(), n pizza[0].size(), mod 1e9 7;vectorvectorvectorint f(k, vectorvectorint(m, vectorint(n)));vectorvectorint apples(m 1, vectorint(n 1)); // 后缀和// 后缀和 与 初始化dp数组for (int i m - 1; i 0; i--){for (int j n - 1; j 0; j--){apples[i][j] apples[i 1][j] apples[i][j 1] - apples[i 1][j 1] (pizza[i][j] A);f[0][i][j] apples[i][j] 0;}} for (int kk 1; kk k; kk){for (int i 0; i m; i){for (int j 0; j n; j){// 选择此刀的切割位置// 水平切, 遍历切的位置for (int a i 1; a m; a){// 上面的一块中至少要有一个苹果if (apples[i][j] apples[a][j]){f[kk][i][j] (f[kk][i][j] f[kk - 1][a][j]) % mod;}}// 垂直切for (int b j 1; b n; b){// 左侧块中至少有一个苹果if (apples[i][j] apples[i][b]){f[kk][i][j] (f[kk][i][j] f[kk - 1][i][b]) % mod;}}}}}return f[k - 1][0][0];}
};
原理思路 apples 数组后缀和用于记录一块披萨中的苹果数量用一块中的左上角来代替此块含有的苹果数。 此题的关键是dp[ k ][ i ][ j ] 的含义代表还剩下 k 刀没切剩下的是左上角为 i j 的披萨状态时的切割方案总数。这是我自己的理解力扣上dp数组定义的含义感觉不如我这样写和解释更直观不过原理肯定是一样的。 知道dp数组的含义就很好写了。 首先计算 apples 数组这个就不用解释了不会的话建议去学习一下前缀和二维前缀和的基础算法就行同时初始化一下dp。 初始化dp数组显然在还需要切0刀剩下最后一块披萨中有苹果时表示切好了是一种情况赋值为1否则不成立赋值为0
f[0][i][j] apples[i][j] 0; 遍历顺序一定是先遍历切割刀数因为就比如一个形状披萨状态下切两刀肯定需要切一刀的状态递推而来后面根据递推式也能看出来。 递推方程两种切法分类讨论 水平切肯定是从第一行下边开始切总不能切空气吧所以是 i 1 开始遍历然后切完后上面的那块中一定要有苹果所以需要判断一下切完此刀后剩下的大块需要再切 kk - 1刀我们就不用再去遍历了dp数组含义就是这个根据这个写出递推式。 递推式f[ kk ][ i ][ j ] (f[ kk ][ i ][ j ] f[ kk - 1 ][ a ][ j ]) % mod; 垂直切与水平切同理直接给出递推式 递推式f[ kk ][ i ][ j ] (f[ kk ][ i ][ j ] f[ kk - 1 ][ i ][ b ]) % mod; 最后返回结果显然在初始状态还剩切k - 1刀时是我们需要的结果状态。 return f[ k - 1 ][ 0 ][ 0 ]; 结束。
