1444. Number of Ways of Cutting a Pizza ======================================= 题目信息 -------- :题号: 1444 :难度: Hard :主题: 动态规划、二维前缀和、切割计数 :原题: `LeetCode 1444 `_ :重点: 用 ``k-1`` 次水平或竖直切割得到 ``k`` 块,每次交出上方或左方部分,最终每块至少含一个苹果 题目重述 -------- 给定字符矩阵 ``pizza``,``A`` 表示苹果,``.`` 表示空格。需要进行 ``k-1`` 次切割,把披萨分成 ``k`` 块。 每次可以沿格子边界水平切割并交出上方部分,或竖直切割并交出左方部分,继续切割剩余部分。要求最终每块至少含一个苹果。请返回合法切割顺序数量对 ``10^9 + 7`` 取模后的结果。 ``1 <= pizza.length, pizza[i].length <= 50``,``1 <= k <= 10``。 自建示例 -------- 水平和竖直切割都可能合法: .. code-block:: text 输入:pizza = ["A.","AA"], k = 2 输出:2 解释:沿两行之间水平切割,或沿两列之间竖直切割,得到的两块都含苹果。 苹果数量少于块数时无解: .. code-block:: text 输入:pizza = ["A"], k = 2 输出:0 解释:唯一苹果不能同时分配到两块披萨中。