2023年8月17日每日一题--1444. 切披萨的方案数

leetcode链接：1444. 切披萨的方案数

题目分析

示例 1：

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

方案一

动态规划杀我，这个题目需要再消化！！！

class Solution {  
    public int ways(String[] pizza, int k) {  
        int row = pizza.length, col = pizza[0].length(), mod = 1000000007;  
        int[][] apple = new int[row][col];  
        int[][][] dp = new int[k][row][col];  
  
        int sum = 0;  
        for (int i = row - 1; i >= 0 ; i--) { // 从右下角向左上角，统计苹果的数据为多少  
            String s = pizza[i];  
             sum = 0;  
            for (int j = col - 1; j >= 0; j--) {  
                if (s.charAt(j) == 'A') sum++;  
                if (i == row - 1) apple[i][j] = sum;  
                else apple[i][j] =  apple[i + 1][j] + sum;  
                dp[0][i][j] = apple[i][j] > 0 ? 1 : 0;  
//                System.out.print("   " + apple[i][j]);  
            }  
//            System.out.println();  
        }  
  
//        System.out.println("sum = " + sum);  
  
        for (int ki = 1; ki < k; ki++) {  
            for (int i = 0; i < row; i++) {  
                for (int j = 0; j < col; j++) {  
  
                    // 按照水平方向去切  
                    for (int l = i + 1; l < row; l++) {  
                        if (apple[i][j] > apple[l][j]) {  
                            dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][l][j]) % mod;  
                        }  
                    }  
  
                    // 按照垂直方向去切  
                    for (int l = j + 1; l < col; l++) {  
                        if (apple[i][j] > apple[i][l]) {  
                            dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i][l]) % mod;  
                        }  
                    }  
                }  
            }  
        }  
  
        return dp[k - 1][0][0];  
    }  
}

结果

解答成功:
执行耗时:9 ms,击败了46.03% 的Java用户
内存消耗:38.7 MB,击败了100.00% 的Java用户

分析

时间复杂度：
O( k * m * n * (m + n) )

空间复杂度：
O( k * m * n )

官方题解

https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/solutions/2387392/qie-pi-sa-de-fang-an-shu-by-leetcode-sol-7ik7/

class Solution {
    public int ways(String[] pizza, int k) {
        int m = pizza.length, n = pizza[0].length(), mod = 1_000_000_007;
        int[][] apples = new int[m + 1][n + 1];
        int[][][] dp = new int[k + 1][m + 1][n + 1];

        // 预处理
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i].charAt(j) == 'A' ? 1 : 0);
                dp[1][i][j] = apples[i][j] > 0 ? 1 : 0;
            }
        }

        for (int ki = 2; ki <= k; ki++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 水平方向切
                    for (int i2 = i + 1; i2 < m; i2++) {
                        if (apples[i][j] > apples[i2][j]) {
                            dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i2][j]) % mod;
                        }
                    }
                    // 垂直方向切
                    for (int j2 = j + 1; j2 < n; j2++) {
                        if (apples[i][j] > apples[i][j2]) {
                            dp[ki][i][j] = (dp[ki][i][j] + dp[ki - 1][i][j2]) % mod;
                        }
                    }
                }
            }
        }
        return dp[k][0][0];
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/solutions/2387392/qie-pi-sa-de-fang-an-shu-by-leetcode-sol-7ik7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。