동적 계획법 - 원주율 외우기

https://algospot.com/judge/problem/read/PI

algospot.com :: PI

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int cache[100001];

int classify(string &N, int a, int b) {
	string M = N.substr(a, b - a + 1);
	if (M == string(M.size(), M[0])) return 1;
	
	bool progressive = true;
	for (int i = 0; i < M.size() - 1; i++) {
		if (M[i + 1] - M[i] != M[1] - M[0]) progressive = false;
	}
	if (progressive && abs(M[1] - M[0]) == 1) return 2;
	bool alternating = true;
	for (int i = 0; i < M.size(); i++) {
		if (M[i] != M[i % 2]) alternating = false;
	}

	if (alternating) return 4;
	if (progressive) return 5;
	return 10;
}

int solution(string &N, int begin) {
	if (begin == N.size()) return 0;
	int& ret = cache[begin];
	if (ret != -1) return ret;

	ret = INF;
	for (int L = 3; L <= 5; L++) {
		if (begin + L <= N.size()) {
			ret = min(ret, solution(N, L + begin) + classify(N, begin, begin + L - 1));
		}
	}
	return ret;
}

void input() {
	int testCase;
	cin >> testCase;

	while (testCase--) {
		string N;
		cin >> N;
		memset(cache, -1, sizeof(cache));
		cout << solution(N, 0) << endl;
	}
}

int main() {
	fastio;
	input();
	 
	return 0;
}