前言：
动态规划，简单来说，就是大事化小，小事化无的艺术~

动态规划具备特点：

• 把原来的问题分解成了几个相似的子问题
• 所有的子问题都只需要解决一次
• 储存子问题的解

动态规划的本质：是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递归关系)

动态规划一般从以下4个角度考虑：
1.状态定义(要求：定义的状态一定要形成递归关系)
2.状态间的转移方程定义
3.状态的初始化
4.返回结果

适用场景：最大值 / 最小值，可不可行，是不是，方案个数

1.斐波那契数列

递归解法：

public int Fibonacci(int n) {
    if(n == 0){
        return 0;
    }
    if(n == 1 || n == 2){
        return 1;
    }
    else{
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

但是，如果 n 非常大的话，递归次数就很多，那么这个算法的性能会非常差

public int Fibonacci(int n) {
    if(n < 2){
        return n;
    }
    // 状态定义及 初始化 F(0),F(1)
    int F0 = 0;
    int F1 = 0;
    int ret = 1;
    // 转移方程 F(i) = F(i-1) + F(i-2)
    for(int i = 2;i <= n;i++){
        F0 = F1;
        F1 = ret;
        ret = F0 + F1;
    }
    return ret;
}

2.字符串分割

思考：
问题：字符串 s 是否可以被分割，需要将状态抽象出来

定义状态F(i)： 字符串 s 的前 i 个字符，是否可以被分割
转移方程： 即：F(i) = ？？？
以题目为例：
F(4)：前四个字符是否可以被分割：true
F(8)：F(4) && [5，8]，是否可以在字典中找到：true

那么也可以：
F(1)：前1个字符是否可以被分割：true
F(8)：F(1) && [2，8]，是否可以在词典中找到

F(1) && [2，8]
F(2) && [3，8]
F(3) && [4，8]
F(4) && [5，8]
F(5) && [6，8]
F(6) && [7，8]
F(7) && [7，8]

F(0) && [1，8]

推导出 ：F(i)：(k < i) && F(k) && [ k+1，i ] 是否可以在词典中找到

我们一般认为 F(0) 应该是 false，因为可以将他它看成是一个空串，在词典中一般是找不到的
但是，若 F(0)为 false 的话，当找 F(4) 的时候，F(4)：F(0) && [1，4]，那么此时 由于 F(0) 为 false，则导致最终结果也为 false，显然是不合理的
因此，F(0) ，虽然可以看作是一个空串，但是它没有实际的状态，只是一个辅助的状态，不代表实际意义，故 F(0) 初始为 true

初始状态： F(0)：true
返回结果： F(字符串长度)：F(s.size() )，F(s.length() )

则代码实现：

public boolean wordBreak(String s, Set<String> dict){
    // 创建状态
    boolean[] canBreak = new boolean[s.length() + 1];
    // 初始化
    canBreak[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        // F(i)：(k < i) && F(k) && [ k+1，i ]
        for (int k = 0; k < i; k++) {
            if(canBreak[k] && dict.contains(s.substring(k,i))){
                canBreak[i] = true;
                break;
            }
        }
    }
    return canBreak[s.length()];
}