【LeetCode 算法】Number of Ways of Cutting a Pizza 切披萨的方案数-记忆化

Number of Ways of Cutting a Pizza 切披萨的方案数

问题描述：

给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。

切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 $10^9+7$ 取余的结果。

$$\begin{gathered} 1<=rows,cols<=50 \\ rows==pizza.length \\ cols==pizza[i].length \\ 1<=k<=10 \\ pizza只包含字{符}^{\prime }{A}^{\prime }{和}^{\prime }{.}^{\prime }。 \end{gathered}$$

分析

关键是切法，只允许横切和竖切。

所以对于一个列数为cols，可以进行cols次竖切，同样行数为rows，可以进行rows次横切。

无论哪种切法，剩余的部分，又是一个独立的整体，再次进行新一轮的切割。

而每次的合法切割，是要确保切出k份，而且每一份里面都要又至少1个apple。

这种方案统计，很自然的可以利用递归的方式枚举。
也就是探索性的，尝试出每个合法的方案。
而在递归的过程中，这个方案结果是非常庞大的。

为了方便计算，这里使用对坐标编号，每个xy都会对应一个idx编号。

可以使用dfs(int idx,int left)表示剩余的pizza是以idx为左上角，合法分割成left的方案数。

如果定义不同的dfs，那么它的过程处理和边界处理都会略有不同。

结束的边界则为

• 如果待切割的区域苹果数量少于人数，那么这个方案不成立，返回0.
• 如果left==1时，此时区域内有至少1个苹果，该方案合法，返回1，否则就是0.
• 然后 进入分割枚举处理。

以上就是整体的思路，为了避免超时，所以需要加memo，同时区域内的apple统计，可以使用二维前缀和。

如果不使用memo，那么时间复杂度为指数级，使用memo，时间复杂度大概就是$O(kmn)$, 空间复杂度 $O(kmn)$.

代码

递归

class Solution {int[][] sum;int[][] memo;int rows,cols;int Mod = (int)1e9+7;String[] mat;public int getidx(int x,int y){return y+ x*cols;} public int ways(String[] pizza, int k) {rows = pizza.length;cols = pizza[0].length();sum = new int[rows+1][cols+1];int cnt  = rows*cols;memo = new int[cnt][k+1];mat = pizza;// process sumprocess(); for(int i = 0;i<cnt;i++){Arrays.fill(memo[i] ,-1); }int res = dfs(0,k);return res; }// 区间内 要分给left 人 苹果的方案数public int dfs(int lu ,int left){if(memo[lu][left]!=-1){return memo[lu][left];}int tot = count(lu);// have applesif(tot<left) return 0;//left <= totif(left==1){return tot>=1?1:0;}// 够分int x0 = lu/cols, y0= lu%cols; // 横切 算上面int res = 0;for(int i = x0;i<rows;i++){//next rowint nr = i+1;if(nr>=rows) break;int cut = y0+nr*cols;int p2 = count(cut);// not enoughif(p2<left-1) continue; int p1 = tot - p2;if(p1<1)continue;res += dfs(cut,left-1);res %=Mod;}// 竖切for(int i = y0;i<cols;i++){//next colsint nc = i+1;if(nc>=cols) break;int cut = nc+ x0*cols;            int p2 = count(cut);// not enoughif(p2<left-1) continue;int p1 = tot -p2;if(p1<1)continue;            res += dfs(cut,left-1);res %=Mod;} return memo[lu][left] = res;} public void process(){for(int i = 1;i<=rows;i++){for(int j = 1;j<=cols;j++){int cur = mat[i-1].charAt(j-1)=='A'?1:0;int a = sum[i][j-1];int b = sum[i-1][j];int c = sum[i-1][j-1];sum[i][j] = a+b-c+cur;}}return ;} public int count(int A){int x0 = A/cols, y0= A%cols; x0++;y0++;     int tot = sum[rows][cols];tot -= sum[x0-1][cols];tot -= sum[rows][y0-1];tot += sum[x0-1][y0-1];return tot;}
}

时间复杂度$O(kMN)$

空间复杂度$O(kMN)$

Tag

Array

Memoization