Leetcode.198.House Robber

题目

给定一个数组, 不能取连续两个相邻的数字, 求最大可以取多少数字.

Input: [1, 2, 3, 1]
Output: 4
Input: [2, 7, 9, 3, 1]
Output: 12

思路

DP, 对于第一个数字, 如果取第i个元素, 就可以加上dp[i-2], 如果不取第i个元素, 就是dp[i-1].

int rob(vector<int>& nums) {
    if (nums.empty())   return 0;
    int n = (int)nums.size();
    vector<int> dp(n+1, 0);
    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[n];
}

总结

仔细分析问题, 找到突破口.