LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 分别对不偷第一间和不偷最后一间两种情况进行动态规划，复用 #198 解法即可，两种情况较大收益者即为结果

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