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

• 动态规划，dp[i] 表示对于 i 间房能获取的最大收益，如果有 1 间房，则最大收益即为该间房的现金，若有 2 间房则为两者中较大者，若有多间房，则对最后一间房 nums[i - 1] 有偷和不偷两种选择，若不偷最后一间房则最大收益等于对 i - 1 间房的最大收益 dp[i - 1]，若偷最后一间房则不能偷前一间房，最大收益为对 i - 2 间房的最大收益与最后一间房收益之和，即 dp[i - 2] + nums[i - 1]，两种选择较大者即为 dp[i]

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