【牛客】动态规划专题一：斐波那契数列

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 处理多个 caseint 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 处理多个 casecout << 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 处理多个 casecout << 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向前遍历到0for (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);}}}
};