給你一個字符串 s 和一個字符串列表 wordDict 作為字典。請你判斷是否可以利用字典中出現(xiàn)的單詞拼接出 s 。
注意：不要求字典中出現(xiàn)的單詞全部都使用，并且字典中的單詞可以重復(fù)使用。

解題思路：完全背包

1、分析

● 完全背包：有N件物品和一個最多能背重量為W的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品都有無限個（也就是可以放入背包多次），求解將哪些物品裝入背包里物品價值總和最大。

——本題可以轉(zhuǎn)換成完全背包的組合！
背包總?cè)萘浚鹤址畇
待背包中裝的物品：字典中的單詞
物品占據(jù)背包重量、價值：單詞在字符串的占位

2、動態(tài)規(guī)劃步驟

(1) 二維數(shù)組dp[i][j]定義：s中長度為j的前綴子串 是否可以被 下標(biāo)前 i 個字典里的單詞 拆分為一個或多個。 ?
從這個定義上可以看出，這個dp數(shù)組是一個boolean類型數(shù)組。
（這里，為了優(yōu)化空間消耗，使用一維數(shù)組dp[j]。為了理解方便，使用二維數(shù)組定義）

(2) 狀態(tài)轉(zhuǎn)移方程 ?
如果dp[ j1 ] = true，并且 ( j1, j2 ) 這個開區(qū)間的子串是字典中的單詞，那么dp[ j2 ]一定也為true！( j2＞j1 )

(3) 初始化 ?
● dp[0] = 0——長度為0的前綴子串是可以被構(gòu)成的（基礎(chǔ)前提）
注意，我們需要考慮 s為空的情況。幸運的是，本題 s長度至少為1。

(4) 遍歷順序 ?
必須先遍歷背包容量，再遍歷物品！
必須先遍歷背包容量，再遍歷物品！
必須先遍歷背包容量，再遍歷物品！

? 怎么理解？——有兩個角度可以理解
——第一個角度，根據(jù)狀態(tài)轉(zhuǎn)移方程我們可以知道，長度為j的前綴子串是否滿足條件，是依賴于長度更小的前綴子串。所以長度更小的前綴子串在填充dp數(shù)組的時候，就需要考慮所有的單詞。因此是【先遍歷背包容量，再遍歷物品】。
——第二個角度，還記得完全背包中的【組合/排序個數(shù)】問題嘛？本題其實我們求的是排列數(shù)，為什么呢？
拿 s = "applepenapple", wordDict = ["apple", "pen"] 舉例。"apple", "pen" 是物品，那么我們要求 物品的組合一定是 "apple" + "pen" + "apple" 才能組成 "applepenapple"。"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我們就是強調(diào)物品之間順序。因此是【先遍歷背包容量，再遍歷物品】。

(5) 舉例：略。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        // dp[i][j]=true：s中長度為j的前綴子串 可以被拆分為一個或多個在字典中出現(xiàn)的單詞 且以wordDict[i]結(jié)尾
        boolean dp[] = new boolean[len+1];
        dp[0] = true;
        // 必須先遍歷背包容量：長度為j的前綴子串 判斷是否滿足拆分條件，要依賴于長度比它小的前綴子串
        for(int j=1; j<=len; j++){
            for(int i=0; i<wordDict.size(); i++){
                String word = wordDict.get(i);
                if(j >= word.length()){ // word長度 ≤ s前綴子串
                    // 以wordDict[i]結(jié)尾，且除去當(dāng)前單詞 長度為j-wordDict[i].length()的前綴子串也滿足條件
                    if(word.equals(s.substring(j-word.length(), j)) && dp[j-word.length()] == true){ 
                        dp[j] = true;
                        if(j == len) return true; // 全部滿足
                        break; // 長度為j的前綴子串已經(jīng)滿足條件，物品不需要再遍歷了
                    }
                }
            }
        }
        return false;
    }
}

Java-2023

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()];
        for(int j=0; j<s.length(); j++){
            for(int i=0; i<wordDict.size(); i++){
                String cur = wordDict.get(i);
                if(j < cur.length()-1) continue; // 繼續(xù)檢查下一個字符串
                int k2 = cur.length()-1;
                int k1 = j;
                for(; k2>=0; k2--){ // 查看是否能完全匹配
                    if(cur.charAt(k2) != s.charAt(k1)) break;
                    k1--;
                }
                if(k2 == -1 && (k1 == -1 || dp[k1])){
                    dp[j] = true;
                    break;
                }
            }
        }
        return dp[s.length()-1];
    }
}