G&R Blog Release Regulation

1444.切披萨的方案数

给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： ‘A’ （表示苹果）和 ‘.’ （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。
切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。

示例 1：输入：pizza = [“A..”,”AAA”,”…”], k = 3 输出：3

对于这个pizza

A.. 
AAA
...

可行的方案有: 先竖着切一刀

A|..
A|AA
.|..

然后剩余部分中间竖着来一刀, 算1种方法

先横着切一刀

A..
---
AAA
...

然后左侧竖着来一刀, 或者右侧竖着来一刀, 算2种方法
解释：上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。
方案有三种
示例 2：输入：pizza = [“A..”,”AA.”,”…”], k = 3 输出：1
示例 3：输入：pizza = [“A..”,”A..”,”…”], k = 1 输出：1

分析:
1.dp[i][j][k] 表示 左上角是 (i,j) 右下角为 (m-1,n-1), 切成k块的方案数
2.状态转移: 选自底向上的推导方式, 当前左上角是 (i,j) 右下角为 (m-1,n-1) 共计切 k 次的方式取决于, 某些切 k-1 次的结果再多切1次, 多切这一次的可能性包括从左往右横着切和从从上往下竖着切
3.什么情况下是可行的切割方式: 必须保证切完之后切掉的被切掉那半块是有苹果的
4.怎么判定被切掉的那半块是有苹果的?
利用 preSum 横着作差 preSum[i][q] - preSum[i][j] > 0, 或者竖着作差 preSum[q][j] - preSum[i][i]>0, 表明这中间是有苹果的
5.最终的状态转移
dp[i][j][k] += dp[i+1..m-1][j][k-1] (如果切完的部分是有苹果的) += dp[i][j+1..n][k-1] (如果切完的部分是有苹果的)
6.preSum[i][i] 表示左上角是(i,j) 右下角是(m-1,n-1)区域包含的苹果数, 所以结合容斥原理自底向上遍历一遍

// 利用容斥原理的前缀和计算, preSum(i,j)算的是任意左上角(i,j)到右下角(m-1,n-1)之间苹果数
int m = pizza.size();
int n = pizza[0].size();
vector<vector<int>> preSum(m+1, vector<int>(n+1));
for (int i = m-1; i >=0; --i) {
  for (int j = n-1; j >=0; --j) {
    preSum[i][j] = preSum[i+1][j] + preSum[i][j+1] - preSum[i+1][j+1] + (pizza[i][j] == 'A'? 1 : 0);
  }
}

状态转移

vector<vector<vector<ll>>> dp(m+1, vector<vector<ll>>(n+1, vector<ll>(k+1, 0)));

// 默认不切(等于切成1块)的方案数为1
for (int i = 0; i < m; ++i) {
  for (int j = 0; j < n; ++j) {
    if (preSum[i][j]) {
      dp[i][j][1] = 1;
    }
  } 
}

for (int i = m-1; i >=0; --i) {
  for (int j = n-1; j >=0; --j) {
    for (int cut = 2; cut <= k; ++cut) {
      // 枚举横向切割的位置
      for (int q = i+1; q < m; ++q) {
        // 如果被切除掉的左边部分是有苹果的, 累加切割成k-1块的方案数
        if (preSum[i][j] - preSum[q][j] > 0) {
            dp[i][j][cut] += dp[q][j][cut-1];
            dp[i][j][cut] %= mod;
        }
      }
      // 枚举纵向切割的位置
      for (int q = j+1; q < n; ++q) {
      // 如果被切除掉的上边部分是有苹果的, 累加切割成k-1块的方案数
        if (preSum[i][j] - preSum[i][q] > 0) {
          dp[i][j][cut] += dp[i][q][cut-1];
          dp[i][j][cut] %= mod;
        }
      }
    }
  }
}

综合 dp 转移以及前缀和, 得到完整答案

typedef long long ll;

class Solution {
 public:
  int ways(vector<string>& pizza, int k) {
    int m = pizza.size();
    int n = pizza[0].size();
    const int mod = 1e9+7;

    // 利用容斥原理的前缀和计算, preSum(i,j)算的是任意左上角(i,j)到右下角(m-1,n-1)之间苹果数 
    vector<vector<int>> preSum(m+1, vector<int>(n+1));
    for (int i = m-1; i >=0; --i) {
      for (int j = n-1; j >=0; --j) {
        preSum[i][j] = preSum[i+1][j] + preSum[i][j+1] - preSum[i+1][j+1] + (pizza[i][j] == 'A' ? 1 : 0);
      }
    }

    vector<vector<vector<ll>>> dp(m+1, vector<vector<ll>>(n+1, vector<ll>(k+1, 0)));
    // 默认不切(等于切成1块)的方案数为1
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (preSum[i][j]) {
          dp[i][j][1] = 1;
        }
      } 
    }

    for (int i = m-1; i >=0; --i) {
      for (int j = n-1; j >=0; --j) {
        for (int cut = 2; cut <= k; ++cut) {
          // 枚举横向切割的位置
          for (int q = i+1; q < m; ++q) {
            // 如果被切除掉的左边部分是有苹果的, 累加所有可切点下, 已经切割成k-1块的方案数
            if (preSum[i][j] - preSum[q][j] > 0) {
              dp[i][j][cut] += dp[q][j][cut-1];
              dp[i][j][cut] %= mod;
            }
          }
          // 枚举纵向切割的位置
          for (int q = j+1; q < n; ++q) {
            // 如果被切除掉的上边部分是有苹果的, 累加所有可切点下, 已经切割成k-1块的方案数
            if (preSum[i][j] - preSum[i][q] > 0) {
              dp[i][j][cut] += dp[i][q][cut-1];
              dp[i][j][cut] %= mod;
            }
          }
        }
      }
    }
    return dp[0][0][k];
  }
};

---

转载请注明来源, from goldandrabbit.github.io