动态规划学习总结一

动态规划

动态规划算法与分治法类似，其基本思想也是将待解决的问题分解为若干个子问题，先求解子问题，然后将这些子问题的解得到原问题的解。与分治法不同的是，适合于动态规划求解的问题，经分解后得到的子问题往往不是互相独立的。在用分治法求解问题的时候，有些子问题被重复计算多次。为了解决这个问题，动态规划用一个表记录所有以解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

动态规划求解步骤

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()];

    }