动态规划问题：单词拆分（DFS、BFS、DP）

139. 单词拆分

题目描述

针对一个非空字符串 s 以及一组包含多个非空单词的列表 wordDict，判断该字符串是否能够通过添加空格的方式被拆分为若干个存在于字典中的单词。

说明：

在拆分过程中，字典中的单词可以被多次使用。
可假设字典中不存在重复的单词。
示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 是由于 “leetcode” 可以被划分为 “leet code”。
示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 是由于 “applepenapple” 可以被划分为 “apple pen apple”。
注意：字典中的单词可以被重复使用。
示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

解题思路分析

（1）DFS思路

1. *未采用记忆化机制的DFS策略