2023-06-30：给你一个 rows * cols 大小的矩形披萨和一个整数 k，

矩形包含两种字符： ‘A’ （表示苹果）和 ‘.’ （表示空白格子），

你需要切披萨 k-1 次，得到 k 块披萨并送给别人，

切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，

将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，

如果水平地切，那么需要把上面的部分送给一个人，

在切完最后一刀后，需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。

由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。

输入：pizza = [“A..”,”AAA”,”…”], k = 3。

输出：3。

答案2023-06-30：

大体过程如下：

算法1：递归法

1.定义常量 mod = 1000000007。

2.定义函数 ways1(pizza []string, k int) int，接收一个披萨矩形和切割次数 k，返回方案数。

3.获取披萨的行数 n 和列数 m。

4.创建一个二维数组 sum，用于记录每个位置左上角区域内的苹果数量的累加和。

5.调用函数 setAppleMatrix，计算 sum 数组。

6.调用函数 process，传入 sum、n、m、初始行、初始列和切割次数 k。

7.在函数 process 中，首先判断当前切割位置的左上角区域内是否包含苹果，若不包含则返回 0。

8.若切割次数 rest 等于 1，表示只需要切割一次，直接返回 1。

9.初始化变量 ways 为 0，表示方案数。

10.在列方向上进行切割，遍历从当前切割位置 col 开始到第 m 列的所有位置。

10.1.若从当前切割位置到当前列的左上角区域内包含苹果，则递归调用 process 函数，切割位置更新为 i+1，切割次数更新为 rest-1，得到的方案数累加到 ways 中，并对 ways 取模。

11.在行方向上进行切割，遍历从当前切割位置 row 开始到第 n 行的所有位置。

11.1.若从当前切割位置到当前行的左上角区域内包含苹果，则递归调用 process 函数，切割位置更新为 i+1，切割次数更新为 rest-1，得到的方案数累加到 ways 中，并对 ways 取模。

12.返回 ways。

算法2：动态规划法

1.定义常量 mod = 1000000007。

2.定义函数 ways2(pizza []string, k int) int，接收一个披萨矩形和切割次数 k，返回方案数。

3.获取披萨的行数 n 和列数 m。

4.创建一个二维数组 sum，用于记录每个位置左上角区域内的苹果数量的累加和。

5.调用函数 setAppleMatrix，计算 sum 数组。

6.创建一个三维动态规划数组 dp，大小为 k+1 * (n+1) * (m+1)，用于记录切割方案数。

7.初始化 dp 数组的第一层，即切割次数为 1 的情况。遍历披萨的所有位置 (r, c)：

7.1.若从当前切割位置到当前位置的左上角区域内包含苹果，则 dp[1][r][c] = 1。

8.从切割次数为 2 开始，逐层计算 dp 数组，直到切割次数为 k。

9.在每一层 level 中，遍历披萨的所有位置 (row, col)，从最后一行和最后一列开始更新 dp 值：

9.1.初始化变量 ways 为 0，表示方案数。

9.2.在列方向上进行切割，遍历从当前切割位置 col 开始到第 m 列的所有位置 c。

9.2.1.若从当前切割位置到当前列的左上角区域内包含苹果，则遍历切割位置 c+1 到 m 的所有位置 s：

9.2.1.1.将 dp[level-1][row][s] 的方案数累加到 ways 中，并对 ways 取模。

9.2.1.2.当遇到包含苹果的位置时，跳出循环。

9.3.在行方向上进行切割，遍历从当前切割位置 row 开始到第 n 行的所有位置 r。

9.3.1.若从当前切割位置到当前行的左上角区域内包含苹果，则遍历切割位置 r+1 到 n 的所有位置 s：

9.3.1.1.将 dp[level-1][s][col] 的方案数累加到 ways 中，并对 ways 取模。

9.3.1.2.当遇到包含苹果的位置时，跳出循环。

9.4.将 ways 赋值给 dp[level][row][col]。

10.返回 dp[k][1][1]。

算法1：

• 时间复杂度：O(n^2 * m^2 * k)

• 空间复杂度：O(n * m)

算法2：

• 时间复杂度：O(n^2 * m^2 * k)

• 空间复杂度：O(k * n * m)

在这两种算法中，n 是披萨的行数，m 是披萨的列数，k 是需要切割披萨的次数。它们具有相同的时间和空间复杂度，因为它们都采用了类似的动态规划方法来计算切割披萨的方式数量。

注意：通过使用前缀和在常数时间内计算给定子矩阵中苹果数量，可以进一步优化时间复杂性，而不是使用apple()函数，但总体复杂性保持不变。

go完整代码如下：

package main

import (
    "fmt"
)

const mod = 1000000007

func ways1(pizza []string, k int) int {
    n := len(pizza)
    m := len(pizza[0])
    sum := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        sum[i] = make([]int, m+1)
    }
    setAppleMatrix(pizza, sum, n, m)
    return process(sum, n, m, 1, 1, k)
}

func process(sum [][]int, n, m, row, col, rest int) int {
    if apple(sum, row, col, n, m) == 0 {
        return 0
    }
    if rest == 1 {
        return 1
    }
    ways := 0
    for i := col; i < m; i++ {
        if apple(sum, row, col, n, i) > 0 {
            ways += process(sum, n, m, row, i+1, rest-1)
            ways %= mod
        }
    }
    for i := row; i < n; i++ {
        if apple(sum, row, col, i, m) > 0 {
            ways += process(sum, n, m, i+1, col, rest-1)
            ways %= mod
        }
    }
    return ways
}

func ways2(pizza []string, k int) int {
    n := len(pizza)
    m := len(pizza[0])
    sum := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        sum[i] = make([]int, m+1)
    }
    setAppleMatrix(pizza, sum, n, m)
    dp := make([][][]int, k+1)
    for i := 0; i <= k; i++ {
        dp[i] = make([][]int, n+1)
        for j := 0; j <= n; j++ {
            dp[i][j] = make([]int, m+1)
        }
    }

    for r := 1; r <= n; r++ {
        for c := 1; c <= m; c++ {
            if apple(sum, r, c, n, m) > 0 {
                dp[1][r][c] = 1
            }
        }
    }

    for level := 2; level <= k; level++ {
        for row := n; row >= 1; row-- {
            for col := m; col >= 1; col-- {
                ways := 0
                for c := col; c < m; c++ {
                    if apple(sum, row, col, n, c) > 0 {
                        for s := c + 1; s <= m; s++ {
                            ways += dp[level-1][row][s]
                            ways %= mod
                        }
                        break
                    }
                }
                for r := row; r < n; r++ {
                    if apple(sum, row, col, r, m) > 0 {
                        for s := r + 1; s <= n; s++ {
                            ways += dp[level-1][s][col]
                            ways %= mod
                        }
                        break
                    }
                }
                dp[level][row][col] = ways
            }
        }
    }
    return dp[k][1][1]
}

func setAppleMatrix(pizza []string, sum [][]int, n, m int) {
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if pizza[i][j] == 'A' {
                sum[i+1][j+1] = 1
            }
        }
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
        }
    }
}

func apple(sum [][]int, a, b, c, d int) int {
    return sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1]
}

func main() {
    pizza := []string{"A..", "AAA", "..."}
    k := 3

    fmt.Println(ways1(pizza, k))
    fmt.Println(ways2(pizza, k))
}

rust完整代码如下：

const MOD: i32 = 1_000_000_007;

fn ways1(pizza: Vec<String>, k: i32) -> i32 {
    let n = pizza.len();
    let m = pizza[0].len();
    let mut sum = vec![vec![0; m + 1]; n + 1];
    set_apple_matrix(&pizza, &mut sum, n, m);
    process(&sum, n, m, 1, 1, k)
}

fn process(sum: &Vec<Vec<i32>>, n: usize, m: usize, row: usize, col: usize, rest: i32) -> i32 {
    if apple(sum, row, col, n, m) == 0 {
        return 0;
    }
    if rest == 1 {
        return 1;
    }
    let mut ways = 0;
    for i in col..m {
        if apple(sum, row, col, n, i) > 0 {
            ways += process(sum, n, m, row, i + 1, rest - 1);
            ways %= MOD;
        }
    }
    for i in row..n {
        if apple(sum, row, col, i, m) > 0 {
            ways += process(sum, n, m, i + 1, col, rest - 1);
            ways %= MOD;
        }
    }
    ways
}

fn ways2(pizza: Vec<String>, k: i32) -> i32 {
    let n = pizza.len();
    let m = pizza[0].len();
    let mut sum = vec![vec![0; m + 1]; n + 1];
    set_apple_matrix(&pizza, &mut sum, n, m);
    let mut dp = vec![vec![vec![0; m + 1]; n + 1]; k as usize + 1];
    for r in 1..=n {
        for c in 1..=m {
            if apple(&sum, r, c, n, m) > 0 {
                dp[1][r][c] = 1;
            }
        }
    }
    for level in 2..=k as usize {
        for row in (1..=n).rev() {
            for col in (1..=m).rev() {
                let mut ways = 0;
                for c in col..m {
                    if apple(&sum, row, col, n, c) > 0 {
                        for s in c + 1..=m {
                            ways += dp[level - 1][row][s];
                            ways %= MOD;
                        }
                        break;
                    }
                }
                for r in row..n {
                    if apple(&sum, row, col, r, m) > 0 {
                        for s in r + 1..=n {
                            ways += dp[level - 1][s][col];
                            ways %= MOD;
                        }
                        break;
                    }
                }
                dp[level][row][col] = ways;
            }
        }
    }
    dp[k as usize][1][1]
}

fn set_apple_matrix(pizza: &Vec<String>, sum: &mut Vec<Vec<i32>>, n: usize, m: usize) {
    for i in 0..n {
        let row = pizza[i].chars().collect::<Vec<char>>();
        for j in 0..m {
            sum[i + 1][j + 1] = if row[j] == 'A' { 1 } else { 0 };
        }
    }
    for i in 1..=n {
        for j in 1..=m {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}

fn apple(sum: &Vec<Vec<i32>>, a: usize, b: usize, c: usize, d: usize) -> i32 {
    sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1]
}

fn main() {
    let pizza = vec![
        String::from("A.."),
        String::from("AAA"),
        String::from("...")
    ];
    let k = 3;
    let res1 = ways1(pizza.clone(), k);
    let res2 = ways2(pizza, k);
    println!("Result 1: {}", res1);
    println!("Result 2: {}", res2);
}

c++完整代码如下：

#include <iostream>
#include <vector>
using namespace std;

const int mod = 1000000007;

void setAppleMatrix(vector<string>& pizza, vector<vector<int>>& sum, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sum[i + 1][j + 1] = (pizza[i][j] == 'A') ? 1 : 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}

int apple(vector<vector<int>>& sum, int a, int b, int c, int d) {
    return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1];
}

void setNear(vector<vector<int>>& sum, vector<vector<int>>& nearr, vector<vector<int>>& nearc, int n, int m) {
    for (int r = 1; r <= n; r++) {
        int right = m + 1;
        int number = 0;
        for (int c = m; c >= 1; c--) {
            int curApple = apple(sum, r, c, n, m);
            if (curApple > number) {
                number = curApple;
                right = c;
            }
            nearc[r][c] = right;
        }
    }
    for (int c = 1; c <= m; c++) {
        int down = n + 1;
        int number = 0;
        for (int r = n; r >= 1; r--) {
            int curApple = apple(sum, r, c, n, m);
            if (curApple > number) {
                number = curApple;
                down = r;
            }
            nearr[r][c] = down;
        }
    }
}

void setRowColSums(vector<vector<int>>& dp, vector<vector<int>>& rs, vector<vector<int>>& cs, int n, int m) {
    rs[n][m] = dp[n][m];
    cs[n][m] = dp[n][m];
    for (int r = n - 1; r >= 1; r--) {
        cs[r][m] = dp[r][m];
        rs[r][m] = (dp[r][m] + rs[r + 1][m]) % mod;
    }
    for (int c = m - 1; c >= 1; c--) {
        rs[n][c] = dp[n][c];
        cs[n][c] = (dp[n][c] + cs[n][c + 1]) % mod;
    }
    for (int r = n - 1; r >= 1; r--) {
        for (int c = m - 1; c >= 1; c--) {
            rs[r][c] = (dp[r][c] + rs[r + 1][c]) % mod;
            cs[r][c] = (dp[r][c] + cs[r][c + 1]) % mod;
        }
    }
}

int process(vector<vector<int>>& sum, int n, int m, int row, int col, int rest);

int ways1(vector<string>& pizza, int k) {
    int n = pizza.size();
    int m = pizza[0].length();
    vector<vector<int>> sum(n + 1, vector<int>(m + 1));
    setAppleMatrix(pizza, sum, n, m);

    return process(sum, n, m, 1, 1, k);
}

int process(vector<vector<int>>& sum, int n, int m, int row, int col, int rest) {
    if (apple(sum, row, col, n, m) == 0) {
        return 0;
    }
    if (rest == 1) {
        return 1;
    }
    int ways = 0;
    for (int i = col; i < m; i++) {
        if (apple(sum, row, col, n, i) > 0) {
            ways += process(sum, n, m, row, i + 1, rest - 1);
            ways %= mod;
        }
    }
    for (int i = row; i < n; i++) {
        if (apple(sum, row, col, i, m) > 0) {
            ways += process(sum, n, m, i + 1, col, rest - 1);
            ways %= mod;
        }
    }
    return ways;
}

int ways2(vector<string>& pizza, int k) {
    int n = pizza.size();
    int m = pizza[0].length();
    vector<vector<int>> sum(n + 1, vector<int>(m + 1));
    setAppleMatrix(pizza, sum, n, m);
    vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= m; c++) {
            if (apple(sum, r, c, n, m) > 0) {
                dp[1][r][c] = 1;
            }
        }
    }
    for (int level = 2; level <= k; level++) {
        for (int row = n; row >= 1; row--) {
            for (int col = m; col >= 1; col--) {
                int ways = 0;
                for (int c = col; c < m; c++) {
                    if (apple(sum, row, col, n, c) > 0) {
                        for (int s = c + 1; s <= m; s++) {
                            ways += dp[level - 1][row][s];
                            ways %= mod;
                        }
                        break;
                    }
                }
                for (int r = row; r < n; r++) {
                    if (apple(sum, row, col, r, m) > 0) {
                        for (int s = r + 1; s <= n; s++) {
                            ways += dp[level - 1][s][col];
                            ways %= mod;
                        }
                        break;
                    }
                }
                dp[level][row][col] = ways;
            }
        }
    }
    return dp[k][1][1];
}

int main() {
    vector<string> pizza = { "A..", "AAA", "..." };
    int k = 3;

    int result1 = ways1(pizza, k);
    int result2 = ways2(pizza, k);

    cout << "Result 1: " << result1 << endl;
    cout << "Result 2: " << result2 << endl;

    return 0;
}

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define mod 1000000007

void setAppleMatrix(char** pizza, int** sum, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sum[i + 1][j + 1] = (pizza[i][j] == 'A' ? 1 : 0);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}

int apple(int** sum, int a, int b, int c, int d) {
    return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1];
}

void setNear(int** sum, int** nearr, int** nearc, int n, int m) {
    for (int r = 1; r <= n; r++) {
        int right = m + 1;
        int number = 0;
        for (int c = m; c >= 1; c--) {
            int curApple = apple(sum, r, c, n, m);
            if (curApple > number) {
                number = curApple;
                right = c;
            }
            nearc[r][c] = right;
        }
    }
    for (int c = 1; c <= m; c++) {
        int down = n + 1;
        int number = 0;
        for (int r = n; r >= 1; r--) {
            int curApple = apple(sum, r, c, n, m);
            if (curApple > number) {
                number = curApple;
                down = r;
            }
            nearr[r][c] = down;
        }
    }
}

void setRowColSums(int** dp, int** rs, int** cs, int n, int m) {
    rs[n][m] = dp[n][m];
    cs[n][m] = dp[n][m];
    for (int r = n - 1; r >= 1; r--) {
        cs[r][m] = dp[r][m];
        rs[r][m] = (dp[r][m] + rs[r + 1][m]) % mod;
    }
    for (int c = m - 1; c >= 1; c--) {
        rs[n][c] = dp[n][c];
        cs[n][c] = (dp[n][c] + cs[n][c + 1]) % mod;
    }
    for (int r = n - 1; r >= 1; r--) {
        for (int c = m - 1; c >= 1; c--) {
            rs[r][c] = (dp[r][c] + rs[r + 1][c]) % mod;
            cs[r][c] = (dp[r][c] + cs[r][c + 1]) % mod;
        }
    }
}

int ways1(char** pizza, int pizzaSize, int k) {
    int n = pizzaSize;
    int m = strlen(pizza[0]);
    int** sum = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        sum[i] = (int*)calloc(m + 1, sizeof(int));
    }
    setAppleMatrix(pizza, sum, n, m);
    int result = process(sum, n, m, 1, 1, k);
    for (int i = 0; i <= n; i++) {
        free(sum[i]);
    }
    free(sum);
    return result;
}

int process(int** sum, int n, int m, int row, int col, int rest) {
    if (apple(sum, row, col, n, m) == 0) {
        return 0;
    }
    if (rest == 1) {
        return 1;
    }
    int ways = 0;
    for (int i = col; i < m; i++) {
        if (apple(sum, row, col, n, i) > 0) {
            ways += process(sum, n, m, row, i + 1, rest - 1);
            ways %= mod;
        }
    }
    for (int i = row; i < n; i++) {
        if (apple(sum, row, col, i, m) > 0) {
            ways += process(sum, n, m, i + 1, col, rest - 1);
            ways %= mod;
        }
    }
    return ways;
}

int ways2(char** pizza, int pizzaSize, int k) {
    int n = pizzaSize;
    int m = strlen(pizza[0]);
    int** sum = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        sum[i] = (int*)calloc(m + 1, sizeof(int));
    }
    setAppleMatrix(pizza, sum, n, m);
    int*** dp = (int***)malloc((k + 1) * sizeof(int**));
    for (int i = 0; i <= k; i++) {
        dp[i] = (int**)malloc((n + 1) * sizeof(int*));
        for (int j = 0; j <= n; j++) {
            dp[i][j] = (int*)calloc(m + 1, sizeof(int));
        }
    }
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= m; c++) {
            if (apple(sum, r, c, n, m) > 0) {
                dp[1][r][c] = 1;
            }
        }
    }
    int result = 0;
    for (int level = 2; level <= k; level++) {
        for (int row = n; row >= 1; row--) {
            for (int col = m; col >= 1; col--) {
                int ways = 0;
                for (int c = col; c < m; c++) {
                    if (apple(sum, row, col, n, c) > 0) {
                        for (int s = c + 1; s <= m; s++) {
                            ways += dp[level - 1][row][s];
                            ways %= mod;
                        }
                        break;
                    }
                }
                for (int r = row; r < n; r++) {
                    if (apple(sum, row, col, r, m) > 0) {
                        for (int s = r + 1; s <= n; s++) {
                            ways += dp[level - 1][s][col];
                            ways %= mod;
                        }
                        break;
                    }
                }
                dp[level][row][col] = ways;
            }
        }
        result = dp[level][1][1];
    }
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            free(dp[i][j]);
        }
        free(dp[i]);
    }
    free(dp);
    for (int i = 0; i <= n; i++) {
        free(sum[i]);
    }
    free(sum);
    return result;
}

int main() {
    char* pizza[] = { "A..", "AAA", "..." };
    int k = 3;
    int result1 = ways1(pizza, sizeof(pizza) / sizeof(pizza[0]), k);
    int result2 = ways2(pizza, sizeof(pizza) / sizeof(pizza[0]), k);
    printf("Result1: %d\n", result1);
    printf("Result2: %d\n", result2);
}

本作品采用《CC 协议》，转载必须注明作者和本文链接