1444.Number of Ways of Cutting a Pizza
===

###### tags: `Hard`,`Array`,`Matrix`,`DP`

[1444. Number of Ways of Cutting a Pizza](https://leetcode.com/problems/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:**


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.

### 解答
#### Python

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        rows, cols = len(pizza), len(pizza[0])

        @cache
        def has_apple(up, left, bottom, right):
            return any(any(pizza[r][c] == 'A' for c in range(left, right)) for r in range(up, bottom))

        @cache
        def dp(up, left, k):
            if k == 1:
                if has_apple(up, left, rows, cols):
                    return 1
            count = 0
            for r in range(up, rows):
                if has_apple(up, left, r+1, cols):
                    count += dp(r+1, left, k-1)
            for c in range(left, cols):
                if has_apple(up, left, rows, c+1):
                    count += dp(up, c+1, k-1)
            return count
        
        return dp(0, 0, k) % (10 ** 9 + 7)

> [name=Yen-Chi Chen][time=Fri, Mar 31, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)