我心匪石
不可转也
dp题，算是少有的能不看任何提示、评论和题解就写出来并一次AC的题了。
简单来说，用dp[i]表示sentence前i个字符中，能够被识别的最多字符数。
如果字典中存在一个长度为len的字符串s，且满足s == sentence.substr(i, len)那么就有：
dp[i - 1 + len] = dp[i - 1] + len
不过记得一直取最大值：
dp[i - 1 + len] = max(dp[i - 1] + len, dp[i - 1 + len])
以及：
dp[i] = max(dp[i], dp[i-1]);
代码如下：
class Solution {
public:
int respace(vector<string>& dictionary, string sentence) {
int len = sentence.size();
vector<int> dp(len + 1);
int ans = 0;
for (int i = 0; i <= len; i++) {
if (i >= 1)
dp[i] = max(dp[i], dp[i-1]);
for (const string &it : dictionary) {
int j = i + it.length();
if (j <= len && sentence.substr(i, it.length()) == it)
dp[j] = max(dp[i] + (int) it.length(), dp[j]);
if (j <= len)
ans = max(ans, dp[j]);
}
}
return len - ans;
}
};
