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