leetcode 5407. 切披萨的方案数(难度:困难)

本题是力扣188期周赛中的最后一题。

一、题目

给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。

切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。

示例 1:

输入:pizza = ["A..","AAA","..."], k = 3
输出:3 
解释:上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。

示例 2:

输入:pizza = ["A..","AA.","..."], k = 3
输出:1


示例 3:

输入:pizza = ["A..","A..","..."], k = 1
输出:1
 

提示:

  • 1 <= rows, cols <= 50, rows == pizza.length, cols == pizza[i].length
  • 1 <= k <= 10
  • pizza 只包含字符 'A' 和 '.' 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza

二、题解(动态规划)

题目简化下来其实就是矩阵切割k-1次切割为k份,每一刀切掉切口上方或者左方一块,要求每一块里必须包含A,求切法总数。

看完题目基本就知道是动态规划类型的题,要不断地从普通状态转换到最简单的状态。一个矩阵可以从不同的行或列切为2份,但是这一刀切下去需要保证两个前提:

  1. 切割出来的左边或者上边部分包含A
  2. 剩余的部分包含A的数量不少于k-1, 因为还要将剩下部分分割给k-1个人。

总的切割方法数量即当前任意切法切割后剩余部分分割给k-1个人的方法数量总和。

这样就将k个人的分割方法计算转换为了k-1个人的分割方法数。直到剩余的A数量比剩余人数少,或者仅剩余1个人,此时就是最简单的状态,可以直接知道余下部分的切割方法。

Javascript代码实现:

var ways = function(pizza, k) {
    let count = 0
    for (let row of pizza) {
        for (let i = 0; i < row.length; i++) {
            row[i] == 'A' && count++
        }
    }
    return cal(pizza, k, count)
};

function cal (pizza, k, countA, record = {}) {
    if (!pizza.length) return 0
    let rows = pizza.length, cols = pizza[0].length
    let recordKey = `${rows}-${cols}-${k}`
    if (recordKey in record) return record[recordKey]

    if (k > countA) {
        record[recordKey] = 0
    } else if (k <= 1) {
        record[recordKey] = 1
    } else {
        record[recordKey] = 0
        let cutA = 0, rest = [...pizza]
        // 计算从各个位置横切的切法
        while (rest.length > 1) {
            const cut = rest.shift()
            for (let i = 0; i < cut.length; i++) if (cut[i] == 'A') cutA++
            // 如果上方没有A,这个切割不合要求,直接跳过
            if (!cutA) continue
            record[recordKey] += cal(rest, k - 1, countA - cutA, record)
        }

        //计算竖切
        cutA = 0
        for (let i = 0; i < pizza[0].length - 1; i++) {
            for (let j = 0; j < pizza.length; j++) if (pizza[j][i] == 'A') cutA++
            if (!cutA) continue
            rest = pizza.map(s => s.slice(i + 1))
            record[recordKey] += cal(rest, k - 1, countA - cutA, record)
        }
    }
    record[recordKey] = record[recordKey] % (Math.pow(10, 9) + 7)
    return record[recordKey]

上述代码中使用了record对象记录已经计算过的右下角rows行cols列分割给k人的分割方法数,以避免递归过程中的重复计算。

¥ 赞赏