动态规划
动态规划算法与分治法类似，其基本思想也是将待解决的问题分解为若干个子问题，先求解子问题，然后将这些子问题的解得到原问题的解。与分治法不同的是，适合于动态规划求解的问题，经分解后得到的子问题往往不是互相独立的。在用分治法求解问题的时候，有些子问题被重复计算多次。为了解决这个问题，动态规划用一个表记录所有以解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
动态规划求解步骤
1 找出最优解的性质，并刻画其结构特征
2 递归地定义最优解
3 以自顶向上的方式计算出最优值
4 根据计算最优值时得到的信息，构造最优解
问题一 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入:s = "leetcode", wordDict = ["leet", "code"]输出:true解释:返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入:s = "applepenapple", wordDict = ["apple", "pen"]输出:true解释:返回 true 因为"applepenapple"可以被拆分成"apple pen apple"。 注意你可以重复使用字典中的单词。
示例 3：
输入:s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出:false
解题思路
第一步，首先，我们先定义一个一维数组dp,长度为string.length + 1,默认dp[0] = true，dp[i]表示的意思就是，string字符串0~i的子串是否能够符合要求;
第二步，然后进行一次二重循环，第一重表示截取子串的起点，第二重表示截取子串的终点，如果当前截取的子串字典中出现过，那么dp[j] = dp[i] && dict.contains(s.substring(i, j))。
来源 链接：https://www.jianshu.com/p/7cfd6eaa905f
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int i = 0; i < s.length(); ++ i){
for(int j = 1 + i; j <= s.length(); ++j){
if(!dp[j])
dp[j] = dp[i] && wordDict.contains(s.substring(i,j));
}
}
return dp[s.length()];
}
