# 1444. Number of Ways of Cutting a Pizza

Given a rectangular pizza represented as a `rows x cols` matrix containing the following characters: `'A'` (an apple) and `'.'` (empty cell) and given the integer `k`. You have to cut the pizza into `k` pieces using `k-1` cuts. 

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

*Return the number of ways of cutting the pizza such that each piece contains **at least** one apple.* Since the answer can be a huge number, return this modulo 10^9 + 7.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/04/23/ways_to_cut_apple_1.png)

```
Input: pizza = ["A..","AAA","..."], k = 3
Output: 3 
Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.
```

**Example 2:**

```
Input: pizza = ["A..","AA.","..."], k = 3
Output: 1
```

**Example 3:**

```
Input: pizza = ["A..","A..","..."], k = 1
Output: 1
```

**Constraints:**

* `1 <= rows, cols <= 50`
* `rows == pizza.length`
* `cols == pizza[i].length`
* `1 <= k <= 10`
* `pizza` consists of characters `'A'` and `'.'` only.

方格上有苹果，每次能沿着行或列切割，并把上面或左边的苹果分出去，要求每次都能分出至少一个苹果，问一共有多少种分法。找所有的情况=> DP/DFS。从（0,0）起点开始，遍历所有可能的切割方式，检查切割后上或左侧是否有苹果。如有，切割后的剩下的格子是独立子问题，因此可以用DFS + memo记忆化递归该子问题。判断指定范围内格子是否有苹果 => Range Sum Immutable 2D。

思路参考自花花

```python
class Solution:
    def ways(self, pizza: List[str], K: int) -> int:
        M, N, MOD = len(pizza), len(pizza[0]), 10 ** 9 + 7
        apple = [[0] * (N + 1) for _ in range(M + 1)]
        memo = [[[-1] * K for _ in range(N)] for _ in range(M)]
        for j in range(N):
            for i in range(M):
                apple[i + 1][j + 1] = apple[i + 1][j] + apple[i][j + 1] - apple[i][j]
                apple[i + 1][j + 1] += 1 if pizza[i][j] == 'A' else 0
        def has(r1, c1, r2, c2):
            return (apple[r2 + 1][c2 + 1] - apple[r1][c2 + 1] - apple[r2 + 1][c1] + apple[r1][c1]) > 0
        def dfs(r, c, k):
            if memo[r][c][k] != -1:
                return memo[r][c][k]
            if k == 0:
                return 1 if has(r, c, M - 1, N - 1) else 0
            res = 0
            for i in range(r, M - 1):
                if has(r, c, i, N - 1):
                    res = (res + dfs(i + 1, c, k - 1)) % MOD
            for j in range(c, N - 1):
                if has(r, c, M - 1, j):
                    res = (res + dfs(r, j + 1, k - 1)) % MOD
            memo[r][c][k] = res
            return res
        return dfs(0, 0, K - 1)
    
```