题目大意:
切披萨的方案数
给你一个 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-解题思路分析/