[LeetCode]Word Break

很直观的递归题目，但是backtracking会超时，我们要用DP来优化。DP[i]表示string的前i个字符能否成功break，我们有递推公式：

• DP[i] = true, if我们有 j, where s[j, i]在字典里，并且DP[i] == true
• 否则，DP[i] = false

时间复杂度O(n^2)，空间复杂度O(n)，代码如下: