<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 {
private:
    int mod = 1000000007;
    int cutDP(int x, int y, vector<vector<int>> &sum, vector<vector<vector<int>>> &dp, int k ){
        if( !sum[y][x] )
            return 0;
 
        if( k == 1 ){
            return 1;
        }
        if( dp[k][y][x] != -1)
            return dp[k][y][x];
        int ans = 0;    

        for( int i = y+1; i < size(sum) ; ++i){
            if( sum[y][x] - sum[i][x] > 0){
                ans = ( ans + cutDP(x,i,sum,dp,k-1) ) % mod;
            }
              
        }    

        for( int i = x; i < size(sum[0]) ; ++i){
            if( sum[y][x] - sum[y][i] > 0){
                ans = ( ans + cutDP(i,y,sum,dp,k-1) ) % mod;
                }
            
        }   

        return dp[k][y][x] = ans;
    }    
public:
    int ways(vector<string>& pizza, int k) {
        int rowSize = pizza[0].size(), colSize = size( pizza );
        vector<vector<int>> sum( colSize+1, vector<int>(rowSize+1,0));
        vector<vector<vector<int>>> dp(vector(k+1, vector(colSize+1, vector(rowSize+1,-1))));

        for( int i = colSize - 1; i >= 0 ; --i)
            for( int j = rowSize - 1; j >= 0; --j )
                                sum[i][j] = (pizza[i][j]=='A') + sum[i][j+1] + sum[i+1][j]-sum[i+1][j+1];  
            
        
        if( sum[0][0] < k )
            return 0;
        
        return cutDP(0,0,sum,dp,k);
    }
};
10000