最大单词分割

使用动态规划算法解决最大单词分割问题。具体步骤如下：

1. 定义一个数组 dp[]，其中 dp[i] 表示从字符串开头到字符串第 i 个字符所形成的最大单词数。
2. 初始化 dp[0] 为 0，表示空字符串不包含任何单词。
3. 从字符串的第一个字符开始遍历，计算其能与前面的字符一起组成多少个单词。遍历到当前字符时，将前面所有可能的单词长度输出，然后更新 dp[i] 为前面所有 dp[j] + 1 的最大值（其中 j<i 且 [j,i] 是一个单词）。
4. 最后返回 dp[n]，即整个字符串最大的单词数。

以下是 Python 代码示例：

def max_word_split(s): n = len(s) dp = [0] * (n+1) dp[0] = 0 for i in range(1, n+1): word_len = [] for j in range(i): if s[j:i] in wordDict: word_len.append(len(s[j:i])) if not word_len: dp[i] = dp[i-1] else: max_word = max(word_len) dp[i] = max(dp[j]+1 for j in range(i-max_word, i)) return dp[n]

其中，wordDict 表示单词列表，需要先预处理出来。