memo[ どこまで作った ] = 最小コスト
const int N = 50 + 1; int memo[N]; string S; vector<string> W; const int inf = 1 << 29; int cost(string a, string b) { if (a.size() != b.size()) return inf; string sa = a; string sb = b; sort(sa.begin(), sa.end()); sort(sb.begin(), sb.end()); if (sa != sb) return inf; int diff = 0; for (int i = 0; i < b.size(); ++i) { diff += a[i] != b[i]; } return diff; } int rec(int n) { if (n == S.size()) return 0; int &ret = memo[n]; if (ret != -1) return ret; int mn = inf; string s; for (int i = 0; n + i < S.size(); ++i) { s += S[n + i]; for (int j = 0; j < W.size(); ++j) { int m = cost(s, W[j]); if (m != inf) { mn = min(mn, rec(n + i + 1) + m); } } } return ret = mn; } class SentenceDecomposition { public: int decompose(string sentence, vector <string> validWords) { S = sentence; W = validWords; fill(memo, memo + N, -1); int ret = rec(0); return ret == inf ? -1 : ret; } };