プログラマー-泥棒

1.質問

質問リンク
説明:
泥棒はある村を強奪しようとしている.この村のすべての家は下図のように丸く配置されている.

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

この村の家は3つ以上100000軒以下です.

money配列の各要素は1000以下の整数である.

I/O例
moneyreturn[1, 2, 3, 1]4

2.解答

問題を解くときに問題を小さな部分に分けて、それから
一部の問題を順番に解決すれば、問題が解決しやすくなります.
この問題で一番難しいのは何ですか.
家はすべて円形に配置されています.
私たちは最初からすべての問題を解決しないで、小さなことから始めることにしました.
そこで、まずすべての家が丸いのではなく、一列に並んでいることを想像してみましょう.
まず完全ナビゲーションから設計を開始します.

フルナビゲーション

#include <vector>
#include <algorithm>

using namespace std;

// 일렬로 나열된 집들을 터는 경우를 모두 탐색하는 함수
int f(int s, int sum, vector<int> *money) {
	// 기저 사례 - 모든 집을 다 털었을 때 그동안 모은 sum 리턴
	if (s >= money->size()) return sum;
    
	// 현재 집을 털지 않고 다음 집으로 넘어가는 경우 vs 현재 집을 털고 다다음 집으로 넘어가는 경우
	return max(f(s + 1, sum, money), f(s + 2, sum + (*money)[s], money));
}

int solution(vector<int> money) {
	return f(0, 0, &money);
}

まず,完全ナビゲーション関数を作成した.
しかし、すべての家に対して回転します.アントンを選ぶからです.
時間の複雑さがO(2^n)になるので、手帳の方法を適用してみましょう.

注釈

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 메모 배열
int memo[1000001];

// f(s) = s번째 집부터 털었을 때 얻을 수 있는 최댓값
int f(int s, vector<int> *money) {
	// 기저 사례 - 모든 집을 털었을 때 0을 리턴
	if (s >= money->size()) return 0;

	int &ret = memo[s];

	if (ret != 0) return ret;
    
	// 현재 집을 털지 않고 다음 집부터 털었을 때 얻을 수 있는 최댓값
    	// vs 
        // 현재 집을 털고 다다음 집부터 털었을 때 얻을 수 있는 최댓값
	return ret = max(f(s + 1, money), (*money)[s] +  f(s + 2, money));
}

int solution(vector<int> money) {
	return f(0, &money);
}

今回は、コメント作成を簡単に適用できます.
しかし、これまで作成した関数は、家を開くコードに焦点を当てていた.
どのようにしてリストされた円形の家屋を掘削問題に変えることができますか?
f(s)=2軒目から強盗を始めたときに得られる最低価格
f(s) = max(f(s + 1), money[s] + f(s + 2));
注記再構成を適用すると,上の点火式が得られた.
今から考えて、上の点火式を利用して
「円形に並んだ家を強奪した時も解決できる」
円形に並んだ家を開けると、
0軒目からn-1軒目まで
最初の家からn番目の家まで別々に考えることができるからです.
では、上の関数を少し私たちが望んでいる形式に変換しましょう.
f(s,e)=s 1家目からe家強盗時に得られる最価値
パラメータとしてe変数が追加されました.
今、円形に並んだ家の最低価格が出ます.int answer = max(f(0, n - 1), f(1, n));0家からn-1家、1家からn家まで、
最高価格は私たちが望んでいる答えです.

上から下への完全なコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int memo1[1000001]; // 0번째 집부터 털 때 쓰는 메모이제이션 배열
int memo2[1000001]; // 1번째 집부터 털 때 쓰는 메모이제이션 배열

int f(int s, int e, int *memo, vector<int> *money) {
	// 기저 사례 - e번째 집까지 털었을 때 0을 리턴
	if (s >= e) return 0;

	int &ret = memo[s];

	if (ret != 0) return ret;

	return ret = max(f(s + 1, e, memo, money), (*money)[s] +  f(s + 2, e, memo, money));
}

int solution(vector<int> money) {
	// 0 ~ n-1까지 터는 경우 vs 1 ~ n까지 터는 경우 
	return max(f(0, money.size() - 1, memo1, &money), f(1, money.size(), memo2, &money));
}

c++であれば、上記のダウンロードコードは通過できるが、javaであれば通過できない.
これは再帰関数であるため、関数呼び出しコストとベースインスタンスを比較する論理が演算されている可能性があります.
でも大丈夫です.
前回リリースされた通学路で説明したように、top-downコードを記述すると、bottom-upコードを簡単に記述することもできます.

Boottom upフルコード

#include <vector>
#include <algorithm>

using namespace std;

int dp1[1000001]; // 0번째 집부터 털 때 쓰는 dp 배열
int dp2[1000001]; // 1번째 집부터 털 때 쓰는 dp 배열

int solution(vector<int> money) {
	int n = money.size();
	dp1[1] = money[0];

	for (int i = 2; i <= n - 1; i++) {
		dp1[i] = max(dp1[i - 1], money[i - 1] + dp1[i - 2]);
	}

	dp2[2] = money[1];

	for (int i = 3; i <= n; i++) {
		dp2[i] = max(dp2[i - 1], money[i - 1] + dp2[i - 2]);
	}

	return max(dp1[n - 1], dp2[n]);
}

bottom-upの初期値設定と重複文設定は不便です.
問題によってはtop-downよりも書きやすいことが多い.
両方ともbottom-upとtop-downの練習をお勧めします