目錄
動態規劃怎么學？
1. 題目解析
2. 算法原理
1. 狀態表示
2. 狀態轉移方程
3. 初始化
4. 填表順序
5. 返回值
3. 代碼編寫
寫在最后：
動態規劃怎么學？
學習一個算法沒有捷徑，更何況是學習動態規劃，
跟我一起刷動態規劃算法題，一起學會動態規劃！
1. 題目解析
題目鏈接：139. 單詞拆分 - 力扣（LeetCode）?
題目很好理解，就是給我們一個字典，
看是否能夠用字典里的字符串拼接成他給的目標字符串 s。
2. 算法原理
1. 狀態表示
dp[ i ] 表示的是從起點到 dp[ i ] 的字符串是否能被字典里的字符串拼接成，
如果成就是 true，否則就是 false
2. 狀態轉移方程
根據最后一個位置的情況來劃分問題，
我們可以把它分成兩個區間來分析，
左區間能否可以拼接成功？右區間是否是字典里的字符串？
所以我們的狀態轉移方程就是：
左區間 == true && 右區間存在字典中，否則就是 false
3. 初始化
為了防止越界加一個虛擬的頭結點即可。
4. 填表順序
從左往右。
5. 返回值
返回 dp 表的最后一個位置
3. 代碼編寫
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> st;for(auto e : wordDict) st.insert(e);vector<bool> dp(s.size() + 1);dp[0] = true;for(int i = 0; i <= s.size(); i++) {for(int j = 0; j < i; j++) {if(dp[j] && st.find(s.substr(j, i - j)) != st.end()) {dp[i] = true;break;}}}return dp[s.size()];}
};寫在最后：
以上就是本篇文章的內容了，感謝你的閱讀。
如果感到有所收獲的話可以給博主點一個贊哦。
如果文章內容有遺漏或者錯誤的地方歡迎私信博主或者在評論區指出~
