算法：切披萨的方案数，3ms解决方案_送披萨算法

题目描述

这是leetcode第1444题。
给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： 'A'（表示苹果）和 '.'（表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。

切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。

示例

输入：pizza = [“A…”,“AAA”,"…"], k = 3
输出：3
解释：上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。

解答

原题解发在了leetcode上，csdn也弄一份吧
本题提供四个方法，逐步优化到比较好的方法。

1.递归（超时）

分析

递归的方法比较容易想得到，但是会超时，不过可以借用这个思想进一步优化。
我们用一个int count(String[] pizza, int row, int col, int k)函数来递归，这个函数解决的是，在以row行，col列为起点的披萨（即这个披萨的左上角为pizza[row][col]，右下角为最右下角），在剩余k次切割机会的情况下，有多少种方案，因为上边和左边的切掉会直接分掉，所以，上边和左边至少要有一个苹果，给出一张披萨，怎么得出方案数呢，分两种情况：横着切和竖着切

• 横着切：我们需要找到从上到下第一个有苹果的行，从这行开始，分为上下两个部分，第一个有苹果的行包括在上面的部分，下面的部分递归用count函数求下面这个部分的披萨在k-1次机会下有多少种切割方案，然后从下面部分划一行给上面部分，再对剩下的下面部分求方案数，一直到下面部分只有一行。在这个过程中，把每次求得的方案数累加起来。
• 竖着切：与横着切差不多，只是一列一列划到左边来计算右边部分的方案数

递归的结束条件是：k == 0，如果此时这个起点的披萨中没有任何一个苹果，则返回0，否则返回1

代码

public int ways(String[] pizza, int k) {
   
        if (pizza == null || pizza.length == 0 || pizza[0] == null || pizza[0].length() == 0 || k <= 0)
            return 0;
        return count(pizza, 0, 0, k-1);
    }

private int count(String[] pizza, int row, int col, int k) {
   
    if (k == 0) {
   
        for (int r = row; r < pizza.length; r++) {
   
            if (pizza[r].substring(col).indexOf('A') != -1) return 1;
        }
        return 0;
    }
    int ri = row, ci = col;
    //找最上面有苹果的行
    while (ri < pizza.length) {
   
        if (pizza[ri].substring(col).indexOf('A') == -1) ri++;
        else break;
    }
    //找最左边有苹果的列
    while (ci < pizza[0].length()) {
   
        boolean hasA = false;
        //已经求得最上边有苹果的行，就从这里开始，可以省点事
        int r = ri;
        while (r < pizza.length) {
   
            if (pizza[r].charAt(ci) == 'A') {
   
                hasA = true;
                break;
            }
            r++;
        }
        if (hasA) break;
        else ci++;
    }
    int res = 0;
    //横着切
    for (int i = ri + 1; i < pizza.length; i++) {
   
        res = (res + count(pizza, i, ci, k-1)) % 1000000007;
    }
    //竖着切
    for (int i = ci + 1; i < pizza[0].length(); i++) {
   
        res = (res + count(pizza, ri, i, k-1)) % 1000000007;
    }
    return res;
}
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

动态规划一

分析

在上面的递归函数中，发现row，col，k这三个参数是会变的，而且这三个参数就能决定一个答案，所以采用一张表（三维数组int[row][col][k]，表示(row, col)为起点剩余k次切割机会的状态有多少种方案。可以看成一个方体，k是层数。在第三个方法优化成二维数组）记录下来，表示在这个状态下的方案数是多少。
接下来，我们需要求出不需要依赖其他状态的信息就能直接给出答案的状态的结果，以后其他的状态需要求出结果需要依赖这些基础状态
能直接得出答案的是剩余切割数为0的状态，如map[i][j][0]，可以直接找(i, j)为起点的披萨还有没有苹果，有就是1，没有就是0。
初始化map[i][j][0]这一步怎么做呢。
下面说明以下怎么得出第0层的表，以下图中，除了苹果A，其他的.格子省略，方案数为1的格子涂成灰色，即以灰色格子的i，j为起点的披萨，一定包含苹果。

• 首先，一个苹果到左上角起点之间为对角的区域是为1的，涂成灰色，因为这个区域为起点的披萨一定包含这个苹果，如下图map[2][2][0] == 1，所以以(2,2)为起点的披萨（红色区域）包含苹果
  
• 然后，这个苹果上边，或左边，或者左上出现了别的苹果，也不需要改变灰色区域
  
• 如果有苹果出现在这个苹果的右上方，则需要更新灰色区域
  

那我们可以这样来求出哪些格子方案数为1：从最后一行从右往左遍历，如果出现了苹果，就记住这个苹果到最左边的距离，并且这行苹果及左边格子涂成灰色，然后看倒数第二行，同样从右往左遍历，有两种情况，一种是出现了比下一行更右边（即离最左边的距离比下一行大）的苹果，那么记住这个距离，然后这里到左边涂成灰色；第二种是没有出现更右边的苹果，那么从右往左遍历直到这个格子到最左边的距离等于记录的距离，那么这里到左边的格子是灰色

距离为3

距离还是3

距离更新为4

还是4

得出k=0的map之后，令k = 1，此时我们需要借助k为0的状态才能得出答案。思路和递归方法时一样，就是分横着切和竖着切，并且每次向上或向左划以行/列。