198. House Robber

Posted on | Edited on | In , |

https://leetcode.com/problems/house-robber/tabs/description/

一个比较明显的动态规划的题，虽然也有更好的解法，但是DP是比较容易想到，而且效率还比较高的那种。

比较轻松地做出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty())
            return 0;
        vector<int> dp(nums.size() + 1);
        dp[0] = 0;
        dp[1] = nums[0];
        for (size_t i = 2; i <= nums.size(); i++) {
            dp[i] = std::max(dp[i-1], nums[i-1] + dp[i-2]);
        }
        return dp[nums.size()];
    }
};