X

LEETCODE 1444. Number of Ways of Cutting a Pizza 解题思路分析

题目大意:

切披萨的方案数

给你一个 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’ 和 ‘.’ 。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1444

解题思路分析:

我们之前多次强调过,看到答案会很大的题目(比如需要对 10^9 + 7 取余),一般来说都要采用动态规划(DP)的方式来思考。对于dp题目,我习惯使用递归加记忆数组的方式来解题。本题也不例外。

递归函数中,我们定义3个重要参数,分别代表披萨当前的开始行与列,以及剩余的刀数。递归中对于当前披萨,我们可以横切或者纵切将其分割成2部分。我们分别尝试每种切割方式,分割后,上半部分或者左半部分是当前要分给他人的一部分,因此我们需要判断该部分内是否含有苹果,如果没有的话,说明当前分割不合理,应继续循环至下一种分割方式。反之如果含有苹果的话,我们可以将剩下的部分(右边或者下边)交给子问题(递归)去解决。循环中所有子问题的返回结果之和,为当前递归的返回结果。递归的结束条件是当k等于1(切完k-1刀)时,查看当前剩下的披萨中是否含有苹果,如果含有的话返回1,反之返回0。

最后再来考虑记忆数组的问题。记忆数组的定义方式是查看递归函数的参数中含有几个可变的变量。本题中,当前列,当前行,以及剩余刀数这三个参数是不断变化的,因此我们需要使用一个三维数组来定义该记忆数组。

实现代码:

Integer memo[][][]; // 记忆数组
public int ways(String[] pizza, int k) {
    char[][] arr = new char[pizza.length][pizza[0].length()];
    // 为了方便,先将pizza转化为二维字符数组
    for(int i=0;i<pizza.length;i++){
        String piz=pizza[i];
        arr[i] = piz.toCharArray();
    }
    // 初始化记忆数组
    memo=new Integer[arr.length][arr[0].length][k+1];
    // 递归求解
    return help(arr, 0,0,k);
}
// arr:披萨数组
// row:当前开始行
// col:当前开始列
// k:剩余刀数
int help(char[][] arr, int row, int col, int k){
    // 切完所有刀后
    if(k==1){
        // 如果当前剩余披萨中含有苹果,返回true,反之返回false
        return hasApple(arr, row, arr.length-1, col, arr[0].length-1)?1:0;
    }
    // 如果记忆数组中存在当前解,返回记忆数组中的值
    if(memo[row][col][k]!=null) return memo[row][col][k];
    // 当前递归返回结果
    long res=0;
    // 分别循环横向每一种切法(上半部分存在1行,2行,3行。。。)
    for(int i=row;i<arr.length-1;i++){
        // 如果上半部分中有苹果
        if(hasApple(arr,row,i,col, arr[0].length-1)){
            // 将下半部分剩余披萨递归至子问题
            // 子问题的返回结果累加至当前返回结果
            res+=help(arr,i+1,col,k-1);
        }
    }
    // 纵切同理
    for(int i=col;i<arr[0].length-1;i++){
        if(hasApple(arr,row,arr.length-1,col,i)){
            res+=help(arr,row,i+1,k-1);
        }
    }
    // 将返回结果取余后转为int型
    int count=(int)(res%1000000007);
    // 保存至记忆数组
    memo[row][col][k]=count;
    return count;
}
// 查看当前区域是否含有苹果 
boolean hasApple(char[][] arr, int rowT,int rowB, int colL, int colR){
    for(int r=rowT;r<=rowB;r++){
        for(int c=colL;c<=colR;c++){
            if(arr[r][c]=='A') return true;
        }
    }
    return false;
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 100.00% of Java online submissions for Number of Ways of Cutting a Pizza.

Memory Usage: 37.3 MB, less than 100.00% of Java online submissions for Number of Ways of Cutting a Pizza.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1444-number-of-ways-of-cutting-a-pizza-解题思路分析/
Categories: leetcode
kwantong: