백준 5582번 C++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;
const int MAX = 4001;
string s1, s2;
int cache[MAX][MAX][2];

int maxstring(int i, int j, int sequence) {
	if (i >= s1.size() || j >= s2.size())
		return 0;

	int &answer = cache[i][j][sequence];
	if (answer != -1)
		return answer;

	answer = 0;
	if (sequence) {
		if (s1[i] == s2[j])
			answer += (maxstring(i + 1, j + 1, sequence) + 1);
		else
			answer = 0;
	}
	else 
		answer = max(maxstring(i, j + 1, 0), maxstring(i + 1, j, 0));	
	if (s1[i] == s2[j])
		answer = max(answer,1 + maxstring(i + 1, j + 1, 1));

	return answer;
}

int main(void) {
	cin >> s1 >> s2;

	memset(cache, -1, sizeof(cache));
	cout << maxstring(0,0,0) << endl;
	return 0;
}