题意理解：

        给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

        这道题目可以用回溯也可以用动态规划来解决。

        这里采用动态规划来解决这个问题，将其转换为一个背包问题。

        wordDict表示可用的元素，其中元素可以被重复使用。

        字符串s就是target，是要凑出来的目标。

        且这里强调顺序，所以这里求的是排列数。

解题思路：

        已知元素集合是wordDict, 元素可以重复使用，所以是完全背包问题。

        其次强调凑出target的顺序，所以这里求排列数，所以双for循环先背包后物品遍历。

        此时dp[j]表示长度为j的字符串是否能被指定的元素组成。其值为true或false.

        

        假设此时字符串长度为j

        其中dp[i]=true 表示长度为i的部分符合条件

        且s.subString(i,j)在元素集合里

        则说明长度为j的字符串可以由元素集里的元素组成，即dp[j]=true.

1.解题

public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp=new boolean[s.length()+1];Arrays.fill(dp,false);dp[0]=true;//无实际意义for(int j=1;j<=s.length();j++){//遍历包for(int i=0;i<j;i++){//遍历元素/*** dp[i]=true表示之前的数组是符合条件* s.subString(i,j) 从当前位置取j个长度，该元素是否在指定元素里、* 若之前的数组符合条件，背包可放入的元素在集合里* 则整个长度为j得到字符串能由元素组成，即dp[j]=true*/if(dp[i]&&wordDict.contains(s.substring(i,j))){//dp[i]=true且dp[j]=true;break;}}}return dp[s.length()];}

2.分析

时间复杂度：O(n^2)

空间复杂度：O(n)