题解 | #牛群的夜间保卫II#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param values int整型vector 
     * @return int整型
     */
    int maxPatrolValue(vector<int>& values) {
        // write code here
        if(values.size() == 1) return values.at(0);
        if(values.size() == 2) return max(values.at(0), values.at(1));
        
        int maxLength = values.size();
        if(values.size() % 2 == 1) {
            values[0] = max(values.at(0), values.back());
            maxLength = values.size() - 1;
        }
        
        vector<int> dp(maxLength, 0);
        dp[0] = values.at(0);
        dp[1] = max(values.at(0), values.at(1));
        int tmp;
        for(tmp = 2; tmp < maxLength; tmp++){
            dp[tmp] = max(dp[tmp-1], dp[tmp-2] + values.at(tmp));
        }

        return dp.back();

    }
};

这道题很恶心的一点是首尾的处理。

先不考虑首尾的问题，可以将题目视作取dp[i]和dp[i-1]的max，其中dp[i]=max(dp[i-1], dp[i-2]+values[i])，记作式a。

考虑首尾时，式a只有在values数组为奇数长度时会出现特殊情况。具体体现在，可能会将首尾元素同时纳入。

明确一点，不管什么情况，首尾元素必然不能同时出现。那么在奇数情形时，我将values[0] = max(values[0], values.back())，然后将数组长度减小一位，这样就成了偶数长度，可以正常处理。