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

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

动态规划：

`dp[i]`表示前`i`头牛最大警戒值，`dp[0] = values[0], dp[1] = max(valuse[0], values[1]);`，递推公式如下：

• 若 `dp[i-2] == dp[i-1]` 则说明`valuse[i-1]`没有被选中，此时选择`values[i]`使得`dp[i]`最大；
• 若 `dp[i-2] != dp[i-1]` 则说明`valuse[i-1]`被选中，此时`dp[i] = max(dp[i-1], dp[i-2] + values[i])`