题目地址：

https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/

给定一个m×nm\times nm×n字符矩阵，只含'A'和'.'。要求将其切成kkk块（即切k−1k-1k−1刀）。每次可以横着切一刀或者竖着切一刀，要求切出的那一块必须含'A'。问有多少种不同的切分方式。

思路是记忆化搜索。设f[x][y][c]f[x][y][c]f[x][y][c]是从(x,y)(x, y)(x,y)到(m−1,n−1)(m-1,n-1)(m−1,n−1)这一部分的不同切分方式。那么我们就是要求f[0][0][k−1]f[0][0][k-1]f[0][0][k−1]。可以直接枚举第一刀是怎么切的，然后递归处理即可。为了快速判断某个子矩阵是否含'A'，我们可以用一个前缀和数组预处理一下。代码如下：

class Solution {public:vector> pre;int MOD = 1e9 + 7;int ways(vector& ps, int k) {int m = ps.size(), n = ps[0].size();pre = vector>(m + 1, vector(n + 1, 0));for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)pre[i][j] = (ps[i - 1][j - 1] == 'A' ? 1 : 0) + pre[i - 1][j] +pre[i][j - 1] - pre[i - 1][j - 1];vector>> f(m, vector>(n, vector(k, -1)));return dfs(0, 0, m, n, k - 1, f);}int dfs(int x, int y, int m, int n, int k, vector>>& f) {if (x == m || y == n) return 0;if (~f[x][y][k]) return f[x][y][k];if (!k) return f[x][y][k] = check(x, y, m - 1, n - 1) ? 1 : 0;int res = 0;for (int i = x; i < m; i++)if (check(x, y, i, n - 1))res = (res + dfs(i + 1, y, m, n, k - 1, f)) % MOD;for (int j = y; j < n; j++)if (check(x, y, m - 1, j))res = (res + dfs(x, j + 1, m, n, k - 1, f)) % MOD;return f[x][y][k] = res;}bool check(int x1, int y1, int x2, int y2) {return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] +pre[x1][y1] > 0;}
};

时空复杂度O(mnk)O(mnk)O(mnk)。