java 解法, 执行用时: 8 ms, 内存消耗: 39 MB, 提交时间: 2023-08-17 07:44:40

class Solution {
    public int ways(String[] pizza, int k) {
        int m = pizza.length, n = pizza[0].length(), mod = 1_000_000_007;
        int[][] apples = new int[m + 1][n + 1];
        int[][][] dp = new int[k + 1][m + 1][n + 1];

        // 预处理
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i].charAt(j) == 'A' ? 1 : 0);
                dp[1][i][j] = apples[i][j] > 0 ? 1 : 0;
            }
        }

        for (int ki = 2; ki <= k; ki++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 水平方向切
                    for (int i2 = i + 1; i2 < m; i2++) {
                        if (apples[i][j] > apples[i2][j]) {
                            dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i2][j]) % mod;
                        }
                    }
                    // 垂直方向切
                    for (int j2 = j + 1; j2 < n; j2++) {
                        if (apples[i][j] > apples[i][j2]) {
                            dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i][j2]) % mod;
                        }
                    }
                }
            }
        }
        return dp[k][0][0];
    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 2.4 MB, 提交时间: 2023-08-17 07:44:17

func ways(pizza []string, k int) int {
    m := len(pizza)
    n := len(pizza[0])
    mod := 1_000_000_007
    apples := make([][]int, m + 1)
    for i := range apples {
        apples[i] = make([]int, n + 1)
    }
    dp := make([][][]int, k + 1)
    for i := range dp {
        dp[i] = make([][]int, m + 1)
        for j := range dp[i] {
            dp[i][j] = make([]int, n + 1)
        }
    }

    // 预处理
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            apples[i][j] = apples[i + 1][j] + apples[i][j + 1] - apples[i+1][j + 1]
            if pizza[i][j] == 'A' {
                apples[i][j] += 1
            }
            if apples[i][j] > 0 {
                dp[1][i][j] = 1
            }
        }
    }

    for ki := 2; ki <= k; ki++ {
        for i := 0; i < m; i++ {
            for j := 0; j < n; j++ {
                // 水平方向切
                for i2 := i + 1; i2 < m; i2++ {
                    if apples[i][j] > apples[i2][j] {
                        dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i2][j]) % mod
                    }
                }
                // 垂直方向切
                for j2 := j + 1; j2 < n; j2++ {
                    if apples[i][j] > apples[i][j2] {
                        dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i][j2]) % mod
                    }
                }
            }
        }
    }
    return dp[k][0][0]
}

python3 解法, 执行用时: 160 ms, 内存消耗: 18.1 MB, 提交时间: 2023-08-17 07:43:45

MOD = 10 ** 9 + 7
class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        m, n = len(pizza), len(pizza[0])
        w = sum(sum(e == 'A' for e in line) for line in pizza)
        query = [[0] * (n + 1) for _ in range(m + 1)]  # 后缀和查询，query[x][y]表示(x, y)到右下角的总共苹果数量
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                query[i][j] = query[i+1][j] + query[i][j+1] - query[i+1][j+1] + (pizza[i][j] == 'A')
        @cache
        def dp(x, y, k):  # 从(x, y)到右下角的这一小块披萨，分出k份的方案数
            nonlocal query, m, n
            if k > query[x][y]:  # 剪枝，如果这一小块披萨上苹果已经不够了，就一个可行方案也没有
                return 0
            elif k == 1:  # 如果这一小块披萨上至少有一个苹果且我们当前只剩下一个人没分到，那么就不用切了，恰好有一个可行方案
                return 1
            res = 0
            for i in range(x + 1, m):  # 横着切
                if query[x][y] - query[i][y] > 0:  # 如果切出去的这部分有苹果，代表这一刀是合法的，下同
                    res = (res + dp(i, y, k-1)) % MOD  # 剩下这一小块披萨分给k-1个人的方案数
            for j in range(y + 1, n):  # 竖着切
                if query[x][y] - query[x][j] > 0:
                    res = (res + dp(x, j, k-1)) % MOD
            # print(x, y, k, res)
            return res % MOD
        return dp(0, 0, k)

python3 解法, 执行用时: 256 ms, 内存消耗: 16.8 MB, 提交时间: 2023-08-17 07:42:38

'''
dp[k][i][j] 表示把坐标 (i,j) 右下方的披萨切割成 k 块披萨的方案数量，
如果 apples[i][j]==1，则初始化 dp[1][i][j]=1，表示当前坐标右下方的披萨符合题目条件，否则为零。

根据题目要求，切一刀将披萨一分为二，每块披萨上都有苹果，所以大披萨的苹果数量，
要严格大于小披萨苹果数量，小披萨的苹果数量，要严格大于零。
'''
class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7
        apples = [[0] * (n + 1) for _ in range(m + 1)]
        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]

        # 预处理
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')
                dp[1][i][j] = 1 if apples[i][j] > 0 else 0

        for k in range(1, k + 1):
            for i in range(m):
                for j in range(n):
                    # 水平方向切
                    for i2 in range(i + 1, m):
                        if apples[i][j] > apples[i2][j]:
                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod
                    # 垂直方向切
                    for j2 in range(j + 1, n):
                        if apples[i][j] > apples[i][j2]:
                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod
        return dp[k][0][0]