leetcode第139题单词拆分

经典完全背包,动态规划:

**dp数组的定义：**以j结尾的字符串是否可以被拆分

**dp数组的初始化：**dp【0】：空串可以被拆分么，可以，这样来表述可能勉强，但是只这这样来，现在i到了指向字符串中的c list中包含leet，dp【0】就应该为true

**状态转移方程：**leetcode可以被拆分，i初始化定义为1，里面都要进行i - 1会是我需要指定的数字。还要注意substring（）是左闭又开区间，j必须从0开始遍历。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {//试着用自己的方式做出来boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for(int i = 1;i <= s.length();i++){for(int j = 0;j < i;j++){if(wordDict.contains(s.substring(j,i)) && dp[j]){dp[i] = true;}}}return dp[s.length()];}
}