ABC 049 C - 白昼夢 を DP でアプローチ

アプローチ

再帰的に全探索してみたが TLE で WA。
随時,最適化を図ってくれる DP が最適と推察。
これなら全探索のように不要部分を探索せず答えが出せる(はず)

問題はコチラ

コードを書く前に、
以下のように組み立ててから挑んだ。

 1.start 地点は、S の先頭とした
 2.先頭から dreamer, dream, erase, eraser を試す。
 3.上記で該当すれば DP として true をメモ
 4.S の先頭から後尾に進んでいくが、3 で True とした位置に辿り着いたら 2 を試す。
 5.4 で検証した結果 該当文字があれば True をメモ
 6.後尾に辿り着くまで 4,5 を繰り返す
 7.DP 最後の配列で true なら Yes, false なら No

コード

以下で AC.

day_dream.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

//dream   5 
//dreamer 7 
//erase   5
//eraser  6

int main() {
	string S; cin >> S;
	int N = S.size();
	
	vector<bool>dp(N+2, false); 
	dp[1] = true;

	for (int i = 1; i <= N; i++) {

		if ((S.substr(i-1, 5) == "dream"|| S.substr(i-1, 5) == "erase") && dp[i]==true) {
			dp[i+5] = true;
		}

		if (S.substr(i-1, 6) == "eraser" && dp[i] == true) {
			dp[i+6] = true;
		}

		if (S.substr(i-1, 7) == "dreamer" && dp[i] == true) {
			dp[i+7] = true;
		}

	}

	//for (auto x : dp)
	//	cout << x << " ";
	//cout << "\n";

	if (dp[N+1]) cout << "YES";
	else cout << "NO";

	//while (1) {}
	return 0;

}

説明不足で申し訳ない。
ガンガン print or cout で経過を表示して
動作確認いただければ幸いです。