给定一个 m x n 的二维矩阵，每个格子要么是 'A'（表示苹果），要么是 '.'（表示空），需要将矩阵切成 k 块，每次切割必须沿着行或列从边缘到边缘切一刀，且每块必须至少包含一个苹果。求切成 k 块的方案数，结果对 10^9+7 取模。请给出实现思路和代码。
考察说明
考察动态规划与二维前缀和的综合应用，以及经典Hard问题的推导能力
回答思路
- 能识别使用动态规划dp[k][i][j]表示切分剩余子矩阵成k块的方案数
- 利用二维前缀和快速判断任意子矩阵是否含苹果
- 正确枚举水平切和垂直切的切割位置，并转移状态
- 最终对结果取模，并处理边界状态初始化
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。