198.house-robber 打家劫舍

问题描述

198.打家劫舍

解题思路

dp[i]表示考虑前i个房间，能窃取到的最大金额。

考虑递推关系:

• 假设第要窃取第i个房间，那么说明第i - 1个房间，肯定没有被窃取，dp[i] = dp[i - 2] + nums[i - 1]。
• 假设不窃取第i个房间，则dp[i] = dp[i - 1]。

综上，dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])。

代码

#include <vector>
using std::vector;
class Solution {
  private:
    int max(int a, int b) {
        return a > b ? a : b;
    }

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