DP1 斐波那契数列

法1：递归

// 递归
#include <iostream>
using namespace std;

int Fibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main() {
    int a;
    while (cin >> a) { // 注意 while 处理多个 case
        int b = Fibonacci(a);
        cout << b << endl;
    }
}

法2：动态规划

// DP
#include <iostream>
using namespace std;

int Fibonacci(int n)
{
    //创建一个数组，保存中间状态的解
    int* F = new int[n + 1];
    //初始化
    F[0] = 0; F[1] = 1;
    //状态公式：F[i] = F[i - 1] + F[i - 2];
    for(int i = 2; i < n + 1; i++)
    {
        F[i] = F[i - 1] + F[i - 2];
    }
    return F[n];
}
int main() {
    int a;
    while (cin >> a) { // 注意 while 处理多个 case
        
        cout << Fibonacci(a) << endl;
    }
}

法3：优化空间复杂度

#include <iostream>
using namespace std;

int Fibonacci(int n)
{
    //状态公式：F[i] = F[i - 1] + F[i - 2];
    //优化空间复杂度 O(n) -> O(1)
    if(n == 0) return 0;
    if(n == 1) return 1;
    int fn = 0, f0 = 0, f1 = 1;
    for(int i = 2; i < n + 1; i++)
    {
        fn = f0 + f1;
        //更新中间状态
        f0 = f1;
        f1 = fn;
    }
    return fn;
}
int main() {
    int a;
    while (cin >> a) { // 注意 while 处理多个 case
        
        cout << Fibonacci(a) << endl;
    }
}

2.分割连接字符串

1、给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。

例如:
给定s=“leetcode”；
dict=[“leet”, “code”].
返回true，因为"leetcode"可以被分割成"leet code".

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

bool wordBreak(string s, unordered_set<string>& dict) {
    // 检查输入是否有效
    if (s.empty() || dict.empty()) {
        return false;
    }

    // 动态规划数组，flag[i]表示s的前i个字符是否可以被拆分
    vector<bool> flag(s.length() + 1, false);
    flag[0] = true; // 空字符串可以被拆分

    // 遍历字符串的每个位置
    for (int i = 1; i <= s.length(); i++) {
        // 从i-1向前遍历到0
        for (int j = i - 1; j >= 0; j--) {
            // 如果前j个字符可以被拆分，且从j到i的子字符串在字典中
            if (flag[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                flag[i] = true;
                break; // 当前位置可以被拆分，跳出内层循环
            }
        }
    }

    // 返回整个字符串是否可以被拆分
    return flag[s.length()];
}

3. 给定一个字符串s和一组单词dict，在s中添加空格将s变成一个句子

这段代码实现了回溯法（深度优先搜索，DFS）来生成所有可能的单词拆分结果。
2、给定一个字符串s和一组单词dict，在s中添加空格将s变成一个句子，使得句子中的每一个单词都是dict中的单词

返回所有可能的结果

例如：给定的字符串s =“catsanddog”,

dict =[“cat”, “cats”, “and”, “sand”, “dog”].

返回的结果为[“cats and dog”, “cat sand dog”].

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& dict) {
        vector<string> result;
        DFS(s, dict, s.length(), "", result);
        return result;
    }

private:
    void DFS(const string& s, const unordered_set<string>& dict, int index, string str, vector<string>& result) {
        // 如果索引小于等于0，说明已经处理完整个字符串
        if (index <= 0) {
            if (!str.empty()) {
                // 去掉最后一个多余的空格，并将结果加入到结果列表中
                result.push_back(str.substr(0, str.length() - 1));
            }
            return;
        }

        // 从当前索引向前遍历，寻找可以拆分的单词
        for (int i = index; i >= 0; i--) {
            // 检查从i到index的子字符串是否在字典中
            if (dict.find(s.substr(i, index - i)) != dict.end()) {
                // 将当前单词加入到路径中，并继续递归处理
                DFS(s, dict, i, s.substr(i, index - i) + " " + str, result);
            }
        }
    }
};