这其实是一个很有价值的题，尤其在自然语言理解方面有重大作用。

一看到字符串是否可以xxx的题目描述，最先想到的就是dp
这种题的基本思路是：设dp[i][j]为子串i..j能够达到的xxx
转移的时候把子串切割，在依次计算

至于这题，思路就是这样的了：
设dp[i][j]为子串i..j可以转换为的大写字母的集合（用二进制+lowbit+ctz实现）
转移就是把dp[i][j]分解为dp[i][k]和dp[k+1][j]，看看可以达到什么样的字母。

不过，如果用这种方法从短到长递推，实践证明，会tle的。

那，怎么办？

往往，记忆化搜索是常数大的代名词，不过这题，它起到了决定性的优化作用！

dfs(i,j,k)表示是否可以用从i到j的字串得到大写字母k，
如果有k->ab
就转化为dfs(i,w,a)&&dfs(w+1,j,b)
这样，就可以用125msAC了！

为什么呢？
其实，记忆化搜索除了好写以外，另一个优势就是只计算必须计算的值，
虽然对于大多数题目，这个特性没有太大价值，但是在此题上便威力无穷。
所以，不妨把记忆化暴搜也看做是一种dp的优化吧：
那就是,对无用的状态进行义不容辞地剪枝

• 赞赞赞 (591) uuuouou 2015-04-28 00:38:20