2023年8月18日每日一题--1388. 3n 块披萨

leetcode链接：1388. 3n 块披萨

题目分析

方案一

头大，想到了可能和 打家劫舍 有关系，没想到dp数组和递推函数怎么做。

class Solution {  
    public int maxSizeSlices(int[] slices) {  
        return Math.max(cal(slices, 0, slices.length -1), cal(slices, 1, slices.length));  
    }  
  
    private int cal(int[] slices, int start, int end) {  
        int N = end - start, n = (end - start + 2) / 3;  
        int[][] dp = new int[N][n + 1];  
  
        dp[0][0] = 0;  
        dp[0][1] = slices[start];  
        dp[1][0] = 0;  
        dp[1][1] = Math.max(slices[start], slices[start + 1]);  
  
        for (int i = 2; i < end - start; i++) {  
            dp[i][0] = 0;  
            for (int j = 1; j <= n; j++) {  
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i + start]);  
//                System.out.print("   dp[i][j] = " + dp[i][j]);  
  
            }  
//            System.out.println();  
        }  
//        System.out.println();  
        return dp[N - 1][n];  
    }  
}

结果

解答成功:
执行耗时:5 ms,击败了82.54% 的Java用户
内存消耗:41.6 MB,击败了90.48% 的Java用户

分析

时间复杂度：
O( 3n * n )

空间复杂度：
O( 3n * n )

官方题解

https://leetcode.cn/problems/pizza-with-3n-slices/solutions/177086/3n-kuai-pi-sa-by-leetcode-solution/

class Solution {
    public int maxSizeSlices(int[] slices) {
        int[] v1 = new int[slices.length - 1];
        int[] v2 = new int[slices.length - 1];
        System.arraycopy(slices, 1, v1, 0, slices.length - 1);
        System.arraycopy(slices, 0, v2, 0, slices.length - 1);
        int ans1 = calculate(v1);
        int ans2 = calculate(v2);
        return Math.max(ans1, ans2);
    }

    public int calculate(int[] slices) {
        int N = slices.length, n = (N + 1) / 3;
        int[][] dp = new int[N][n + 1];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        dp[0][0] = 0;
        dp[0][1] = slices[0];
        dp[1][0] = 0;
        dp[1][1] = Math.max(slices[0], slices[1]);
        for (int i = 2; i < N; i++) {
            dp[i][0] = 0;
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i]);
            }
        }
        return dp[N - 1][n];
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/pizza-with-3n-slices/solutions/177086/3n-kuai-pi-sa-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。