code/1444.number-of-ways-of-cutting-a-pizza.cpp

class Solution
{
    using ll = long long;
    static const int MOD = 1000 * 1000 * 1000 + 7;
    int m, n, gk;
    vector<vector<vector<ll>>> dp;
    vector<vector<int>> acc_row;
    vector<vector<int>> acc_col;

    int search(const vector<string> &pz, int k, int row, int col)
    {
        if (row >= m || col >= n)
            return 0;
        if (dp[k][row][col] != -1)
            return dp[k][row][col];

        ll ret = 0;
        int row_apple_cnt = 0;
        for (int i = row; i < m; ++i) {
            row_apple_cnt += acc_row[i][n] - acc_row[i][col];
            if (row_apple_cnt) {
                if (k > 1) {
                    ret = (ret + search(pz, k - 1, i + 1, col)) % MOD;
                } else {
                    ret = 1;
                    break;
                }
            }
        }
        int col_apple_cnt = 0;
        for (int j = col; j < n; ++j) {
            col_apple_cnt += acc_col[m][j] - acc_col[row][j];
            if (col_apple_cnt) {
                if (k > 1) {
                    ret = (ret + search(pz, k - 1, row, j + 1)) % MOD;
                } else {
                    ret = 1;
                    break;
                }
            }
        }

        return (int) (dp[k][row][col] = ret % MOD);
    }

  public:
    int ways(vector<string> &pz, int k)
    {
        m = pz.size(), n = pz[0].size(), gk = k;

        dp = vector<vector<vector<ll>>>(k + 1, vector<vector<ll>>(m + 1, vector<ll>(n + 1, -1)));
        acc_row = vector<vector<int>>(m + 1, vector<int>(n + 1));
        acc_col = vector<vector<int>>(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                acc_row[i][j + 1] = acc_row[i][j] + (pz[i][j] == 'A' ? 1 : 0);
                acc_col[i + 1][j] = acc_col[i][j] + (pz[i][j] == 'A' ? 1 : 0);
            }
        }

        return search(pz, k, 0, 0);
    }
};