完全平方数

有点理解子规模减少之后，变化的方向了。
1,4，9,16在 肯定要选择刚好比 n 小的平方数的一个，这样，问题的规模就减少了，由于子问题有可能在以前就出现过，我们可以从子问题一个一个推上去运算，从而产生了动态规划。，

最小操作次数使数组元素相等

被秀了一波。
发现这种题目有一个特征就是不关心数组内部元素的绝对次序，只关心数组的相对大小，对于每一次操作，对n-1个元素增大，就相当于对一个元素减小。所以适合反着做。将所有的数减少到最小的那个元素就可以了。

单词搜索2

140. 单词拆分 II
     给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入:
s = “catsanddog”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
输出:
[
“cats and dog”,
“cat sand dog”
]

原来这道题考回溯。
构建好字典树之后，如果每一个节点都是一个分割点，那么将会产生 2 的 n 次方 的分支，所以时间复杂度还是很高的。
如果还是沿用以前的动态规划先判断一个字符串是否可以拆分，自底向上会产生大量重复的计算。
所以采用了一种自底向上的方法。

class Trie{
   public boolean isEnd;
   public Trie [] children;
   Trie(){
       this.isEnd=false;
       this.children = new Trie[26];
   }
   public void insert(String word){
       int n = word.length();
       Trie cur = this;
       for(int i=0;i<n;++i){
           char ch = word.charAt(i);
           int idx = ch - 'a';
           if(cur.children[idx]==null){
               cur.children[idx]=new Trie();
           }
           cur=cur.children[idx];
       }
       cur.isEnd=true;
   }
}
class Solution {
    Trie headNode ;
    Set<String> ret = new HashSet<>();
    StringBuilder ans = new StringBuilder();
    public void dfs(int start,int index,String s,Trie root,StringBuilder ans){
        if(index == s.length()){
            if(start==index){
                ans.delete(ans.length()-1,ans.length());//删除最后一个空格。
                ret.add(ans.toString());
                ans.append(" ");
            }
            return;
        } 
        char ch = s.charAt(index);
        int idx = ch-'a';
        if(root.children[idx]!=null){
            if(root.children[idx].isEnd){//当前是一个结束点，从头开始搜索。
                String temp = s.substring(start,index+1)+" ";
                ans.append(temp);
                dfs(index+1,index+1,s,headNode,ans);
                ans.delete(ans.length()-temp.length(),ans.length());
            }
           
            //当前不是结束点，继续搜索：
            dfs(start,index+1,s,root.children[idx],ans);
            
        }
        return ;
        
    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        //再一次构建字典树。
        Trie root=new Trie();
        headNode = root;
        for(String str:wordDict){
            root.insert(str);
        }
        StringBuilder ans = new StringBuilder();
        dfs(0,0,s,root,ans);
        return new ArrayList<String>(ret);

    }
}