打家劫舍|| 和 3n块披萨 的不同

先记一下 打家劫舍的进阶

• 排成一排的房子
• 排成一圈的房子
• 排成二叉树的房子

不变的是不能偷相邻的房子。自顶向下是打劫了第0家开始，自底向上是打劫了第n-1家开始的。
动态规划第一步是先确定状态和选择。
选择就是 抢或不抢
状态就是 房子的索引
如果采用自顶向下递归法，就会存在重叠子问题，但是可以用备忘录来进行优化。

也可以采用自底向上递推的方式来解题，在这基础上可以降维，降低空间复杂度。

第二题的题解：

int rob(int[] nums){
    int n = nums.length;
    if(n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

int robRange(int[] nums, int start, int end){
    int dp_i_2 = 0, dp_i_1 = 0;
    int dp_i = 0;
    for(int i = end; i >= start; i--){
        dp_i = Math.max(dp_i_2 + nums[i], dp_i_1);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

其他题的题解戳 https://mp.weixin.qq.com/s/z44hk0MW14_mAQd7988mfw

3n快披萨问题 （阿里3.10笔试第二题）

跟打家劫舍||的区别在于：披萨拿走一块，相当于拿走3块，是会让原本不相邻的披萨变成相邻的，所以它能取的披萨小于打家劫舍能打劫的房子数。
因此，我们在打家劫舍的解法中再加上一个数量的约束状态就可以了。

class Solution {
    public int maxSizeSlices(int[] slices) {
        if(slices == null || slices.length == 0) return 0;
        if(slices.length == 1) return slices[0];
        if(slices.length == 2) return Math.max(slices[0], slices[1]);

        int len = slices.length;
        int n = len / 3;    //因为是拿走1块，就会去掉2块，所以/3。
        return Math.max(dp(slices, 0, len-2, n), dp(slices, 1, len-1, n));
    }
    public int dp(int[] slices, int start, int end, int n){
        if(start == end) return slices[start];
        int len = end - start + 1;

        //再加一个状态 披萨块 
        int[][] dp = new int[len][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 < len; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.max(dp[i-2][j-1] + slices[start+i], dp[i-1][j]);
            }
        }

        return dp[len-1][n];
    }
}