SRM411 Div1 Easy

250
メモ化する。memo[どこまで作った] = 最小値

const int N = 50 + 1;

int memo[N];
vector<string> W;
string S;

int rec(int idx)
{    
  if (idx == S.size()) return 0;  
  if (memo[idx] != -1) return memo[idx];

  int mn = inf;

  for (int i = 0; i < W.size(); ++i) {
    if (idx + W[i].size() <= S.size()) ; else continue;
    string s = W[i];
    string t = S.substr(idx, W[i].size());
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    if (s != t) continue;
    int cnt = 0;
    for (int j = 0; j < W[i].size(); ++j) {
      cnt += S[idx + j] != W[i][j];
    }
    mn = min(mn, rec(idx + W[i].size()) + cnt);
  }

  return memo[idx] = mn;
}

class SentenceDecomposition {
public:
  int decompose(string S_, vector <string> W_) 
  {
    S = S_;
    W = W_;    
    fill(&memo[0], &memo[N - 1], -1);
    int ret = rec(0);    
    return ret == inf ? -1 : ret;
  }

};