3n 块披萨【LC1388】
给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：
你挑选 任意 一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
没想出来转化，正好复习一下打家劫舍
思路
该问题可以转化为在环形数组slices中取不相邻的k个数，求最大和。【数学归纳法证明可得，也可以通过观察得到】
环形数组与普通数组的区别在于，首尾元素不能同时取，因此可以进行2次dp
确定dp数组（dp table）以及下标的含义
dp[i][j]：表示在数组 nums 的前i个数中选择j个不相邻的数的最大和。。
确定递推公式
dp数组如何初始化
dp[0][1] = nums[0]; dp[1][1] = Math.max(nums[0],nums[1]);
确定遍历顺序
从前往后遍历nums，枚举j
实现
class Solution { public int maxSizeSlices(int[] slices) { int n = slices.length; int a = f(slices, 0, n - 2); int b = f(slices, 1, n - 1); return Math.max(a, b); } public int f(int[] nums, int start, int end){ int n = nums.length, k = n / 3; int[][] dp = new int[n][k + 1]; dp[start][1] = nums[start]; dp[start + 1][1] = Math.max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++){ for (int j = 1; j <= k; j++){ dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + nums[i]); } } return dp[end][k]; } }
复杂度
时间复杂度：O ( n k )
空间复杂度：O ( n k )
