題目： LeetCode - 198. House Robber

題目說明

給一個陣列代表每間房子的搶劫價值，不能搶連續的兩間房子，求能搶劫的最大價值。

解題思路

使用動態規劃的思路，dp[i] 代表到第 i - 1 間能搶到的最大價值，遍歷 nums，若是決定第 i - 1 間要搶，則 dp[i] 為 dp[i - 2] + nums[i]，若是不搶則為 dp[i - 1]，兩者取較大者即可。

參考解法

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