Leetcode:198. House Robber(week 9)

Description:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

解題思路：

題意為給定一個數組，數組的每個位置表示一個房子，數組的值為錢的數量，相鄰的數不能同時獲得，否則會驚動警察，其本質就是在一列數組中取出一個或多個不相鄰數，使其和最大。 這是一道動态規劃問題。 可以采用動态規劃的方法實作。我采用的算法是周遊一遍，然後周遊的同時将不相鄰的數加起來取最大值，時間複雜度為O(1),代碼如下：

class Solution {
public:
    int rob(vector<int>& nums) {
        int a = , b = ;
        for (int i = ; i < nums.size();i++) {
            if (i%== ) {
                if (a+ nums[i] > b) {
                    a = a + nums[i];
                } else {
                    a = b;
                }
            } else {
                if (b+ nums[i] > a) {
                    b = b + nums[i];
                } else {
                    b = a;
                }
            }
        }
        if (a > b) return a;
        else return b;
    }
};