Leetcode House Robber II

Leetcode House Robber II関連コード,本コードはdpアルゴリズムを用いて関連問題を解決するが,本アルゴリズムの鍵はループの存在をループを持たない場合に劣化させることであり,ループを持たない場合には動的正規化がかなり容易であり,以下はコードおよび関連テストである.アルゴリズムの複雑さはO(n)である.

#include 
#include 
using namespace std;

// the circumstance of circle can be divided into two case
// First: We choose the last, which means that the nearest two of it cannot be choose. And then
//        the max of it should be no_circle[1 --> i-2] + nums[i];
// Second: We doesn't choose the last, which means that nearest two of it can be choose or not.
//         And then, the max of it should be no_circle[0 --> i-1];
// And the result of the [0 --> i] with circle is the maximum of the former two condition.
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }

        int len = nums.size();
        vector<vector<int> > max_longer(len, vector<int>(2, 0));
        max_longer[0][0] = nums[0];

        int max = nums[0];
        // preprocess the record before the common one
        if (len <= 3) {
            for (int i = 0; i < len; i ++) {
                max = max > nums[i]? max : nums[i];
            }
        } else {
            max_longer[1][0] = nums[0] > nums[1]? nums[0] : nums[1];
            max_longer[1][1] = nums[1];

            max_longer[2][0] = nums[0] + nums[2] > nums[1]? nums[0] + nums[2] : nums[1];
            max_longer[2][1] = nums[2] > nums[1]? nums[2] : nums[1];
        }

        for (int i = 3; i < len; i ++) {
            // for the max result
            int choose = nums[i] + max_longer[i - 2][1];
            int not_choose = max_longer[i - 1][0];
            max = choose > max? choose : max;
            max = not_choose > max? not_choose : max;

           // for the from 0 to i without circle max
           choose = nums[i] + max_longer[i - 2][0];
           not_choose = max_longer[i - 1][0];
           max_longer[i][0] = choose > not_choose? choose : not_choose;

           // for the from 1 to i without circle max
           choose = nums[i] + max_longer[i - 2][1];
           not_choose = max_longer[i - 1][1];
           max_longer[i][1] = choose > not_choose? choose : not_choose;
        }
        return max;
    }
};

int main(int argc, char * argv[]) {
    Solution so;
    vector<int> test(5, 0);
    test[0] = 1;
    test[1] = 5;
    int re = so.rob(test);
    cout<<"max:"<return 0;
}