题解 | #不能连续吃草的牛II# 分类讨论 DP

知识点

分类讨论 DP

思路

环形排列，我们可以分类讨论是否取第一个房子和最后一个房子来进行分类讨论

其余的部分和上一道题完全一致。

时间复杂度

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int eatGrass(vector<int>& nums) {
        int f[1005][2];
        int n = nums.size();
        if(n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);

        int res = 0;
        // 不取第n间 取第1间, 不取第2间
        memset(f, 0, sizeof f);
        for (int i = 3; i < n; i ++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i - 1];
        }
        res = max(res, max(f[n - 1][0], f[n - 1][1]) + nums[0]);

        // 不取n - 1间 取第n间 不取第一间
        memset(f, 0, sizeof f);
        for (int i = 2; i < n - 1; i ++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i - 1];
        }
        res = max(res, max(f[n - 2][0], f[n - 2][1]) + nums[n - 1]);

        // 第1间和n间 都不取
        memset(f, 0, sizeof f);
        for (int i = 2; i < n; i ++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i - 1];
        }
        res = max(res, max(f[n - 1][0], f[n - 1][1]));
        return res;
    }

};