关于动态规划【力扣139.单词拆分的思考】

1、可以逆向思考题目问题题目如果可以利用字典中出现的一个或多个单词拼接出s则返回true。字典中的单词可以重复使用。逆向思考转化题目意思字符串s是否能由字典中的单词组成。字符串s相当于背包字典中的单词相当于物品。问是否能装满背包可以无限次取物品2、因为字符串非空所以j从1开始3、递推公式里面的dp[i] true用来表示当前位置的前面字符串可由字典里的单词组成4、物品字典里的每个的单词的长度不会超过书包字符串的长度比如假设书包是app,单词是apple,物品最多遍历到app如果再继续遍历单词毫无意义因为app肯定不能由apple组成。所以遍历单词的时候位置遍历到背包容量的最大就可以了。5、递推公式如果当前被截取的字符串是字典里的单词并且前面的字符串都可由字典里的单词组成则说明整个字符串都可由字典里的单词组成。6、当前状态依赖于前一个状态的问题就像动态规划。拼接出ss就像背包字典里的单词可以重复使用就像完全背包。所以推出整道题是动态规划的完全背包应用问题。本题就是dp[i]的状态依赖于dp[j]的状态。比如如果当前j 3i 3在字典里找到了单词dp[0] true就可以推出dp[j] true也就是dp[3] true下一轮循环假设循环到了j 4i 3截取字符串从3开始长度为4-31这个长度为1的单词出现在了字典里同时dp[i]此时是dp[3]在上一轮循环中已经推出dp[3] true所以这一轮循环推出dp[j] ture也就是dp[4] true接下来继续向后循环直到推出dp[s.size()]的状态