原题链接:
https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/

非常好的一道题 尤其整个将子问题划分的思想可以说是非常经典了

分析过程

代码

记忆化搜索 - 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int ways(vector<string>& pizza, int k) {
        const int MOD = 1e9 + 7;
        int m = pizza.size() , n = pizza[0].size();
        int s[m + 1][n + 1];
        memset(s,0,sizeof s);
        // 计算前缀和数组 用于判断是否存在苹果即是否可切
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + (pizza[i][j] & 1) ;
            }
        }

        // 获取前缀和数组 (x1,y1,x2,y2) 区域的值
        function<int(int,int,int,int)> get = [&](int x1,int y1,int x2,int y2) -> int{
            return s[x2][y2] - s[x2][y1] - s[x1][y2] + s[x1][y1];
        };

        int memo[k][m][n];
        // -1 表示没有计算过
        memset(memo,-1,sizeof memo);

        // c i j : 剩余可切的刀数 (i,j) 当前矩阵左上角的位置
        function<int(int,int,int)> dfs = [&](int c,int i, int j) -> int{
            // 递归边界 无法再切
            if(c == 0){
                // 如果当前区域有一个 苹果 则满足条件 直接分掉 可以算是一种分法
                return get(i,j,m,n) ? 1 : 0;
            }            

            // 定义为引用 因为要同步在计算过程中更新memo 的状态
            int &res =  memo[c][i][j];
            
            if(res != -1){
                return res;
            }

            res = 0;

             // 开始切 左上角是已经分好 因此整体往右下进行枚举(程序中的坐标顶点在左上位置)
            // 垂直切 枚举j2
            for(int j2 = j;j2 < n ; j2++){
                if(get(i,j,m,j2)){
                    res = (res + dfs(c- 1,i,j2)) % MOD;
                }
            }

            for(int i2 = i ; i2 < m ; i2++){
                if(get(i,j,i2,n)){
                    res = (res + dfs(c-1,i2,j)) % MOD;
                }
            }

            return res;
        };

        return dfs(k - 1,0,0);
    }
};