题解 | #牛群的夜间保卫II# 动态规划

原题力扣213打家劫舍2：https://leetcode.cn/problems/house-robber-ii/description/

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

时间复杂度：O(n)，遍历两次数组

空间复杂度：O(n)，存储dp数组