题目描述：

给定一个字符串和一个字符串数组，判断是否存在将字符串任意划分后得到的子字符串都是字符串数组的子集

方法一：动态规划

首先，确定dp数组下标以及含义，dp[i]表示s[0,i]是否是字符串数组的子集。
确定递推公式，枚举结束位置end，在0到end之间枚举开始位置start,当s[0,start]是set的子集，如果s[start,end]也是set的子集,推出 $d p [e n d] = t r u e$
从递推公式可以看出dp[j]是依赖于前面先推出的值，我们需要先初始化dp[0]为true,即空集为集合的子集。

alt

确定遍历顺序，从上图可以看出遍历顺序是从左到右

javascript
java

function wordDiv( s ,  dic ) {
    // write code here
    var dp=[s.length+1];
    var set=new Set(dic);
    dp[0]=true;
    for(let i=1;i<s.length+1;i++ ){
        for(let j=0;j<i;j++){
            if(dp[j]&&set.has(s.substring(j,i))){
                dp[i]=true;
                break;
            }
        }
    }
    return dp[s.length];
}
module.exports = {
    wordDiv : wordDiv
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串一维数组 
     * @return bool布尔型
     */
    public boolean wordDiv (String s, String[] dic) {
        // write code here
        HashSet<String> set = new HashSet<>();
        for(String word: dic){
            set.add(word);//先移除重复字符串
        }
        boolean[] dp = new boolean[s.length() + 1];//dp[i]表示s字符串中前i个字符是不是set的子集
        dp[0] = true;//空串可以被词表中的词表示
        for(int end = 1; end <= s.length(); end++){
            for(int start = 0; start < end; start++){
                if(dp[start] && set.contains(s.substring(start, end))){
                    //s[0:start]是set的子集，s[start:end]也是set的子集，所以s[0:end]是set的子集，dp[end]=true
                    dp[end] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

复杂度：

时间复杂度： $O(n^{2})$ ,双重循环。
空间复杂度： $O (n)$ ,dp数组和集合set均占用空间

题解 | #单词拆分(一)#

题目描述：

方法一：动态规划

复杂度：