微信网站是多少,阿里有做网站,装修公司联系方式汇总,建设公司排名1. 题目
给你一个 rows x cols 大小的矩形披萨和一个整数 k #xff0c;矩形包含两种字符#xff1a; ‘A’ #xff08;表示苹果#xff09;和 ‘.’ #xff08;表示空白格子#xff09;。 你需要切披萨 k-1 次#xff0c;得到 k 块披萨并送给别人。
切披萨的每一刀…1. 题目
给你一个 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先用dp方法求出以i,j位置为右下角左上角为0,0的区域的苹果数量建立3维数组dp[i][j][k]表示切完k次后剩余蛋糕左上角 在i, j位置时的方案数初始化dp[0][0][0] 1样本维度为切的次数 k状态维度这次切之前的状态蛋糕左上角位置 i, j状态转移这次切完后蛋糕左上角位置横向切nij竖向切i, nj切的次数 1转移条件切出去的蛋糕当中有苹果用上面求得的苹果数量dp公式求得最后求结果总和最后的一块蛋糕中有苹果sum dp[i][j][k-1]
class Solution {
public:int ways(vectorstring pizza, int k) {int m pizza.size(), n pizza[0].size(), i, j, sum 0;vectorvectorint app(m,vectorint(n,0));for(i 0; i n; i){if(pizza[0][i]A)sum;app[0][i] sum;}sum 0;for(i 0; i m; i){if(pizza[i][0]A)sum;app[i][0] sum;}for(i 1; i m; i){for(j 1; j n; j){app[i][j] (pizza[i][j]A? 1 : 0) app[i-1][j]app[i][j-1]-app[i-1][j-1];}}//求得以i,j为左下角的矩形中的苹果数量vectorvectorvectorint dp(m,vectorvectorint(n,vectorint(k,0)));//dp[i][j][k]表示切完k次后剩余蛋糕左上角 在i,j位置时的方案数dp[0][0][0] 1;int ni, nj, appcount;//下一个转移状态的位置for(int cut 1; cut k; cut)for(i 0; i m; i){for(j 0; j n; j){if(dp[i][j][cut-1] ! 0)//上一次cut完后剩余蛋糕左上角在i,j{for(ni i1; ni m; ni){ //横向切切完后的剩余左上角为 ni, jappcount app[ni-1][n-1]-(j0 ? app[ni-1][j-1]:0)-(i0?app[i-1][n-1]:0)(i0j0 ? app[i-1][j-1] : 0);if(appcount ! 0)dp[ni][j][cut] (dp[ni][j][cut]dp[i][j][cut-1])%1000000007;}for(nj j1; nj n; nj){ //竖向切appcount app[m-1][nj-1]-(i0?app[i-1][nj-1]:0)-(j0?app[m-1][j-1]:0)(i0j0 ? app[i-1][j-1] : 0);if(appcount ! 0)dp[i][nj][cut] (dp[i][nj][cut]dp[i][j][cut-1])%1000000007;}}}}sum 0;for(i 0; i m; i)for(j 0; j n; j){appcount app[m-1][n-1]-(j0?app[m-1][j-1]:0)-(i0?app[i-1][n-1]:0)(i0j0 ? app[i-1][j-1]:0);if(appcount ! 0)sum (sumdp[i][j][k-1])%1000000007;}return sum;}
};40 ms 8.5 MB
