题解 | #牛群的夜间保卫# 动态规划 打家劫舍

怎么答案与题目不符，题目说围成一圈，实际上是按没围的方法才对，也是醉了

原题：https://leetcode.cn/problems/house-robber/solutions/263856/da-jia-jie-she-by-leetcode-solution/

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

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

空间复杂度：O(n)，使用了dp数组