【玩转算法】（初始）动态规划

🍁1）DP定义

🍁2）斐波那契

牛客网_oj

int Fibonacci(int n ) {
    // write code here
    if(n ==0){
        return 0;
    }
    if(n == 1 || n ==2){
        return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
}

class Solution {
public:
    int Fibonacci(int n) {
    //分析
    //1.状态：F(i)第i项的值
    //2.状态转换方程：F(i) = F(i-1)+F(i-2)
    //3.初始状态：F(0) = 0; F(1) = 1
    //4.返回: F(n)

    //我们要保存中间状态的解。就需要一个数组。
    //先创建一个数组
    int* F = new int[n+1];//注意这里的 n+1；
    //初始化为初始状态
    F[0] = 0;
    F[1] = 1;
    //状态转换方程 ：F(i) = F(i-1)+F(i-2)
    for(int i = 2; i<=n; i++){
        F[i] = F[i-1]+F[i-2];
    }
    return F[n];
    
//优化
    if(n==0) return 0;
    if(n==1) return 1;
    int fn，fn1 = 0，fn2 = 1;
    for(int i = 2; i<=n; i++){
        fn = fn1 + fn2;
        fn1 = fn2;
        fn2 = fn;
    }
    return fn;

//再优化
    int a = 0,b = 1;
    while(n--){
        b = a+b;
        a = b-a;
    }
    return a;
    }
};

🍁3）字符串分割

牛客网_oj

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        //注意这里的被分割是指，能在词典中找到。
        // 方法：动态规划
        // 状态：
        // 子状态：前1，2，3，...,n个字符能否根据词典中的词被成功分词
        // F(i): 前i个字符能否根据词典中的词被成功分词

        // 状态递推：
        // F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false
        // 在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典
        // 中找到，则F(i)为true

        // 初始值：
        // 对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始
        // 空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单
        // 的例子进行验证
        // F(0) = true

        // 返回结果：F(n)

        //实现
        if(s.empty()){ return false; }
        if(dict.empty()){ return false; }

        //创建一个数组保存子状态，便于后面状态使用
        vector<bool> can_break(s.size() + 1, false);

        // 初始化F(0) = true
        can_break[0] = true;

        for (int i = 1; i <= s.size(); i++){
            for (int j = i - 1; j >= 0; j--){
            // F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false
            // 第j+1个字符的索引为j
                if (can_break[j] && dict.find(s.substr(j, i - j)) != dict.end()){
                    can_break[i] = true;
                    break;
                }
            }
        }
        return can_break[s.size()];
    }
};