打家劫舍

class Solution {
 public:
  int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) {
      return nums[0];
    }
    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n; ++i) {
      dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
  }
};

如果是环形的话，则分别考虑以下两种情况

• 选第一个而不选最后一个
• 选最后一个而不选第一个

注意边界条件

class Solution {
 public:
  int rob(vector<int>& nums) {
    int n = nums.size(), ans = 0;
    if (n == 1) {
      return nums[0];
    } else if (n == 2) {
      return max(nums[0], nums[1]);
    }
    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n - 1; ++i) {
      dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    ans = max(ans, dp[n - 2]);
    dp[1] = nums[1];
    dp[2] = max(nums[1], nums[2]);
    for (int i = 3; i < n; ++i) {
      dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    ans = max(ans, dp[n - 1]);
    return ans;
  }
};