LeetCode 1444 - 切披萨的方案数（周赛）

题目描述

1444. 切披萨的方案数

解法一：DP（C++）

详细参考 雪融之时. 的解

统计可能数，一来挺容易行到用动态规划

状态： 我们每次切完都是接着处理剩下的部分，那么可以记 $dp[i][j][k]$ 表示可能的切法， $(i,j)$表示剩余披萨的左上角为，当前披萨被切分为$k$块

转移方程： $dp[x][y][k+1]=dp[i][j][k]if(切分的两部分都有苹果)$，其中记原来的左上角为 $(i,j)$，切分后新的左上角为 $(x,y)$

对于是横切还是竖切，就通过穷举了

最后讲一下，怎么判断切分的部分上是否有苹果？这个思想还是挺有趣的

$nums[i][j]$ 表示以 $(0,0)$ 为左上角，$(i,j)$为右下角的矩形区域的苹果数，那么任一区域（左上角为$(sr,sc)$，右下角为$(er,ec)$）包含的苹果数就可以通过 $nums[er][ec]?nums[sr?1][ec]?nums[er][sc?1]+nums[sr?1][sc?1]$ 求得

typedef long long ll;class Solution {
    
public:int ways(vector<string>& pizza, int k) {
    const ll MOD = 1e9+7;int row = pizza.size(), col = pizza[0].length();vector<vector<int>> nums(row, vector<int>(col, 0));if(pizza[0][0]=='A') nums[0][0] = 1;for(int i=1;i<row;i++) nums[i][0] = nums[i-1][0]+(pizza[i][0]=='A');for(int j=1;j<col;j++) nums[0][j] = nums[0][j-1]+(pizza[0][j]=='A');for(int i=1;i<row;i++)for(int j=1;j<col;j++)nums[i][j] = nums[i-1][j]+nums[i][j-1]-nums[i-1][j-1]+(pizza[i][j]=='A');vector<vector<vector<ll>>> dp(row, vector<vector<ll>>(col, vector<ll>(k+1, 0)));dp[0][0][1] = 1;for(int x=2;x<=k;x++){
    for(int i=0;i<row;i++){
    for(int j=0;j<col;j++){
    if(!dp[i][j][x-1]) continue;;for(int z=i+1;z<row;z++){
    if(hasapple(nums, i, j, z-1, col-1)&&hasapple(nums, z, j, row-1, col-1)){
    dp[z][j][x] += dp[i][j][x-1];dp[z][j][x] %= MOD;}}for(int z=j+1;z<col;z++){
    if(hasapple(nums, i, j, row-1, z-1)&&hasapple(nums, i, z, row-1, col-1)){
    dp[i][z][x] += dp[i][j][x-1];dp[i][z][x] %= MOD;}}}}}ll ans= 0;for(int i=0;i<row;i++)for(int j=0;j<col;j++)ans += dp[i][j][k];ans %= MOD;return ans;}bool hasapple(vector<vector<int>>& nums, int sr, int sc, int er, int ec){
    int p1 = 0, p2 = 0, p3 = 0;if(sr!=0 && sc!=0) p1 = nums[sr-1][sc-1];if(sr!=0) p2 = nums[sr-1][ec];if(sc!=0) p3 = nums[er][sc-1];return nums[er][ec]-p2-p3+p1>0;
}};

解法二：记忆递归（Python）

详细参考 java_Lee的解

递归思路是很简单，就是我切完这一刀，我下一刀怎么切的事。关于切分来的部分怎么保证有?，java_Lee 用了一个表来记录第一个苹果出现的行和列，而且 java_Lee 也在题解中证明了切走左上无?的行列不影响递归结果，那这样的话，每次就对第一个?出现位置的右下部分进行切分，每次切分的结果都能保证有?了

至于记忆递归，就是将一些已经处理过的递归请款打表记录下来，下次遇到同样状况的递归直接查表

最后就是怎么切的问题，这里 java_Lee 主要把横切和竖切的情况分开来讨论了，每次递归都分别记录了横切可能的方案数和竖切可能的方案数

class Solution:def ways(self, pizza: List[str], k: int) -> int:MOD = int(1e9+7)row, col = len(pizza),  len(pizza[0])table = [{
    (row, col):(0,0)} for _ in range(k)]first_apple = [[None] * col for _ in range(row)]def FisrtApple(r, c):'''定义对first_apple的访问方法，避免越界'''return (row, col) if r>= row or c >= col else first_apple[r][c]for r in range(row)[::-1]:for c in range(col)[::-1]:first_apple[r][c] = (r, c) if pizza[r][c] == 'A' else tuple(map(min, zip(FisrtApple(r+1, c), FisrtApple(r, c+1))))if first_apple[r][c] != (row, col):table[0][first_apple[r][c]] = (1, )def dfs(r, c, remain):if (r, c) in table[remain]: return table[remain][r, c]nr, nc = FisrtApple(r+1, c)across = (dfs(nr, nc, remain)[0] + (nr-r)*sum(dfs(nr, nc, remain - 1))) % MODnr, nc = FisrtApple(r, c+1)vertical = (dfs(nr, nc, remain)[1] + (nc-c)*sum(dfs(nr, nc, remain - 1))) % MODtable[remain][r, c] = (across, vertical)return (across, vertical)r0, c0 = FisrtApple(0, 0)return sum(dfs(r0, c0, k-1)