在本題中，我們是要把一個字符串，判斷是否能用給的字符串數(shù)組中的單詞進行拆分，如果可以則返回true，不能的話則返回false。這個題一開始看無法與背包問題聯(lián)系在一起。但仔細考慮，就是用物品（給的字符串數(shù)組中的單詞）去裝背包（給定的字符串）。如果可以湊成，那么就返回true。

并且題目中所說的單詞可以重復使用，也就是完全背包問題。并且我們要考慮，這個題是否需要考慮遍歷順序拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 舉例。

“apple”, “pen” 是物品，那么我們要求 物品的組合一定是 “apple” + “pen” + “apple” 才能組成 “applepenapple”。

“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我們就是強調(diào)物品之間順序。
所以我們要先遍歷背包再遍歷物品。并且可以重復使用，

dp[i] : 字符串長度為i的話，dp[i]為true，表示可以拆分為一個或多個在字典中出現(xiàn)的單詞

如果確定dp[j] 是true，且 [j, i] 這個區(qū)間的子串出現(xiàn)在字典里，那么dp[i]一定是true。（j < i ）。

所以遞推公式是 if([j, i] 這個區(qū)間的子串出現(xiàn)在字典里 && dp[j]是true) 那么 dp[i] = true。

從遞推公式中可以看出，dp[i] 的狀態(tài)依靠 dp[j]是否為true，那么dp[0]就是遞推的根基，dp[0]一定要為true，否則遞推下去后面都都是false了。

那么dp[0]有沒有意義呢？

dp[0]表示如果字符串為空的話，說明出現(xiàn)在字典里。

但題目中說了“給定一個非空字符串 s” 所以測試數(shù)據(jù)中不會出現(xiàn)i為0的情況，那么dp[0]初始為true完全就是為了推導公式。

下標非0的dp[i]初始化為false，只要沒有被覆蓋說明都是不可拆分為一個或多個在字典中出現(xiàn)的單詞

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] valid = new boolean[s.length() + 1];valid[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i;  j++) {if (set.contains(s.substring(j, i)) && valid[j]) {valid[i] = true;}}}return valid[s.length()];}
}

注意，本題中創(chuàng)建了一個新的 HashSet 實例，并使用 wordDict 集合的元素進行初始化。這意味著 set 中的所有元素都將是 wordDict 中的元素，但不包含任何重復項，因為 HashSet 是一個不允許重復元素的集合。
s.substring(j,i)表示截取字符串s下標從j到i的字串，這里是左閉右開的區(qū)間。所以j只能小于i，如果等于i的話，下面截取的時候就會出錯。