問題の説明

泥棒はある村を強奪しようとしている.この村のすべての家は下図のように丸く配置されている.

各家には隣接する家と防犯装置が接続されているため、隣接する家を2軒強奪すると警報が鳴る.
どの家にもお金が入った並びのお金がある場合は、泥棒が盗むことができるお金の最高価格を返すために解関数を書いてください.

せいげんじょうけん

この村の家は3軒以上10万軒以下です.
money配列の各要素は1000以下の整数です.

I/O例

moneyreturn[1, 2, 3, 1]4

Solution

#include <string>
#include <vector>
#define MAX 1000001
using namespace std;

int DP1[MAX];
int DP2[MAX];

int solution(vector<int> money) {
    DP1[0] = money[0];
    DP1[1] = money[0];
    DP2[1] = money[1];

    for(int i = 2; i < money.size()-1; i++){
        DP1[i] = max(DP1[i-1], DP1[i-2] + money[i]);
    }
    for(int i = 2; i < money.size(); i++){
        DP2[i] = max(DP2[i-1], DP2[i-2] + money[i]);
    }
    return max(DP1[money.size()-2], DP2[money.size()-1]);
}

もし最初の家を強盗したら?それとも強盗はありませんか?この二つの状況によって、異なる判断を下すべきだ.
まず、最初の家を強奪したら、自然に最後の家を強奪することはできません.家が円形に配置されていると思ったら、最後の家は最初の家に隣接しているので、強盗はできません.
2軒目も同じです.2軒目の家を強盗したら、最後の家を強盗することができます.
この二つの状況について考えが違うと、すぐに解決できます.

DP[i] = MAX(DP[i-1], DP[i-2] + money[i]

どちらの場合も共通の点火式を共有する.今の立場から見れば、今の位置からお金を稼ぐのが有利かどうかを区別しなければならない.お金を借りる場合は、2つの格のDP値と現在位置のmoney値を加える必要があります.
どうせDPテーブルはずっと更新してるすべての状況に対して、無計画にドアを回すのは効率的ではありません.このように更新し続けると、すべての状況の最後の位置が最大限の強盗の時にお金が現れます.
すぐに思いつくのは難しいに違いない.DPはかなり抽象的な概念だからです.DPの特性上、点火式を見つけるとすぐに解けるので、より多くの練習と経験が必要です.最初はこの点火式を見つけられずにやりましたが、少し考えを変えれば一気に解決できます.