<p>Given a rectangular pizza represented as a <code>rows x cols</code>&nbsp;matrix containing the following characters: <code>&#39;A&#39;</code> (an apple) and <code>&#39;.&#39;</code> (empty cell) and given the integer <code>k</code>. You have to cut the pizza into <code>k</code> pieces using <code>k-1</code> cuts.&nbsp;</p>

<p>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.</p>

<p><em>Return the number of ways of cutting the pizza such that each piece contains <strong>at least</strong> one apple.&nbsp;</em>Since the answer can be a huge number, return this modulo 10^9 + 7.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/ways_to_cut_apple_1.png" style="width: 500px; height: 378px;" /></strong></p>

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;AAA&quot;,&quot;...&quot;], k = 3
<strong>Output:</strong> 3 
<strong>Explanation:</strong> The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;AA.&quot;,&quot;...&quot;], k = 3
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;A..&quot;,&quot;...&quot;], k = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rows, cols &lt;= 50</code></li>
	<li><code>rows ==&nbsp;pizza.length</code></li>
	<li><code>cols ==&nbsp;pizza[i].length</code></li>
	<li><code>1 &lt;= k &lt;= 10</code></li>
	<li><code>pizza</code> consists of characters <code>&#39;A&#39;</code>&nbsp;and <code>&#39;.&#39;</code> only.</li>
</ul>

class Solution {
public:
    int ways(vector<string>& pizza, int k) {
        const int MOD = 1000000000 + 7;
        int m = pizza.size();
        int n = pizza[0].size();
        int dp[51][51][10] = {};    // dp[i][j][p] is the result begin from pizza[i][j] when k = p + 1
        int cnt[51][51] = {};       // cnt[i][j] represents the remaining apples from pizza[i][j]
        for(int i = m - 1; i >= 0; --i)     // suffix sum
            for(int j = n - 1; j >= 0; --j) {
                cnt[i][j] += cnt[i + 1][j] + cnt[i][j + 1] - cnt[i + 1][j + 1] + (pizza[i][j] == 'A');
                dp[i][j][0] = cnt[i][j] > 0;        // dp[i][j][k = 1] is 1 when there is at least one apple
            }
        for (int i = m - 1; i >= 0; --i)
            for (int j = n - 1; j >= 0; --j)
                for (int p = 1; p < k; ++p)     // * see the explanation at the end
                    if (dp[i][j][p - 1]) {  // if dp[i][j][p - 1] is 0, dp[i][j][p] should also be 0, continue
                        for (int ii = i + 1; ii <= m; ++ii)
                            if (cnt[i][j] != cnt[ii][j])    // add one cut before row ii, check if the cut is valid
                                dp[i][j][p] = (dp[i][j][p] + dp[ii][j][p - 1]) % MOD;
                        for (int jj = j + 1; jj <= n; ++jj)
                            if (cnt[i][j] != cnt[i][jj])
                                dp[i][j][p] = (dp[i][j][p] + dp[i][jj][p - 1]) % MOD;
                    }
        return dp[0][0][k - 1];
        /*
        Explanation - Following the logical workflow, the 3 for layers should be as follows. 
        But we can try to improve the cache hit ratio by moving the for loop of p to the inner layer, 
        because there is no data dependency.
        for (int p = 1; p < k; ++p)
            for (int i = m - 1; i >= 0; --i)
                for (int j = n - 1; j >= 0; --j)
        */
    }
};
9100