0%

198. House Robber

发表于 更新于 分类于 阅读次数：
本文字数： 437 阅读时长 ≈ 1 分钟

2018年5月2日 下午3:54
House Robber - LeetCode

从这道题可以看出动态规划也是可以用遍历去解释的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        std::vector<int> dp(nums.size()+1, 0);
        
        dp[0] = nums[0];
        dp[1] = nums[1] > nums[0] ? nums[1]:nums[0];
        //这里的遍历对象是：0~1 0~2 0~3 0~4 .... 0~(n-1)
        //这里的数字是只下标！
        for(int i = 2; i < nums.size(); i++){
            dp[i] = max((dp[i-2]+nums[i]), dp[i-1]);
        }
        
        return dp[nums.size()-1];
    }
};