1LCR 102. 目标和
分析：分成加法和减法两个集合
#include<iostream>
#include<vector>
using namespace std;
//目标和
vector<int>nums = { 1,1,1,1,1 };
int target = 3;
int dfs(int index, int sum)
{//我前面老是错就是这一步出的问题，&&intdex==nums.size否则数组不是每个数都用到if (sum == target && index == nums.size()) return 1; if (index >= nums.size()) return 0;return dfs(index + 1, sum + nums[index] * -1) + dfs(index + 1, sum + nums[index]);
}int main()
{cout << dfs(0, 0) << endl;//分成加法和减法集合 各自子集都是相加
//l+r=sum sum就是nums所有 元素和
//l-r=target
//l=（t+sum）/2 l不能整除说明没有组合满足
//可以整除：把l看成一个容器，然后问题就转化为nums中选容器装满l的方法数int sum = 0; //计数nums总和for (auto i : nums)sum += i;int left = 0;if (abs(target) > sum || (sum + target) % 2 != 0) return 0;else left = (sum+target) / 2;vector<int>dp(left + 1);dp[0] = 1;//i循环代表选择物品范围到哪里for (int i = 0; i < nums.size(); i++) //遍历物品{for (int j = left; j >= nums[i]; j--) //遍历容量 倒序是因为每个物品只能用一次cout << (dp[j] += dp[j - nums[i]]) << " ";cout << endl;}return 0;
}斐波那契数列：
logO(n):从底到顶
#include<iostream>
#include<vector>
using namespace std;vector<int>memo(100,-1);
int fibonacci(int index) //记忆化 上到下递推 O(n)
{if (memo[index] != -1)return memo[index];if (index == 0)return 0;if (index == 1)return 1;return memo[index] = fibonacci(index - 1) + fibonacci(index - 2);
}int main()
{int n;cin >> n;cout << fibonacci(n) << endl;vector<int>dp(n+1,0); //dp 下到上递推 O(logn)dp[1] = 1;for (int i = 2; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2];cout << dp[n] << endl;return 0;
}983. 最低票价
#include<iostream>
#include<vector>
using namespace std;
vector<int>durations = { 1,7,30 }; //存储天数的数组
//dfs 前 to 后
int dfs(int i, vector<int>costs, vector<int>days)
{if (i == days.size())return 0;int ans = INT_MAX;for (int k = 0, j = i; k < 3; k++){while (j < days.size() && days[i] + durations[k] > days[j])j++;ans = min(ans, dfs(j, costs, days) + costs[k]);}return ans;
}int main()
{vector<int>days = { 1,2,3,4,5,6,7,8,9,10,30,31 };vector<int>costs = { 2,7,15 };cout << dfs(0, costs, days) << endl;//dp 后 to 前vector<int>dp(days.size()+1);int n = days.size();dp[n] = 0;for (int i = n - 1; i >= 0; i--) //dfs就是这个for替代 i：当前指向{int ans = INT_MAX;for (int k = 0, j = i; k < 3; k++) //（1,7,30）三种方案{while (j < days.size() && days[i] + durations[k] > days[j]) //当前天+（1,7,30）方案 <= days[j] j索引就是我的后续j++;ans = min(ans, dp[j] + costs[k]); //三个方案花费选最小}dp[i] = ans;}for (auto i : dp)cout << i << " ";return 0;
}91. 解码方法
这道题的理解：
注意这个return 1和dp[n]=1；
我们先说dfs，以123为例子，从1-3不停递归，直到越界，我们就知道匹配成功，返回1，然后开始匹配2个，又直到越界，利用这个”1“一直往前推。
然后dp就是dfs的傀儡，因为越界就成功，返回1；
#include<iostream>
#include<string>
#include<vector>
using namespace std;int dfs(string s,int i)
{//说明匹配成功if (i >= s.size()) return 1;int ans = 0;if (s[i] == '0') //之前匹配模式有问题ans = 0;else{//s[i]!=0ans = dfs(s, i + 1); //i字符匹配if (i + 1 < s.size() && (s[i] - '0') * 10 + s[i + 1] - '0' <= 26) //符合结合条件ans += dfs(s, i + 2); //i和i+1一起匹配；然后跳到i+2开始。} return ans;
}int main()
{string str("1123");cout << "dfs:" << dfs(str, 0) << endl << endl;int n = str.size();vector<int>dp(n + 1); //这个dp含义：把当前这个算上，以及后面的字符；一共有多少种拼法dp[n] = 1;for (int i = n - 1; i >= 0; i--){int ans;if (str[i] == '0')ans = 0;else{ans= dp[i + 1]; //只选当前的if (i + 1 < n && (str[i] - '0') * 10 + str[i] - '0' <= 26)ans+= dp[i + 2]; //选当前和其下一个}dp[i] = ans;}cout << "dp:";for (auto i : dp)cout << i << " ";return 0;
}解码方法2：
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;long mod = 1000000007; //答案和 10^9+7取余long dfs(int index, string str)
{long ans = 0;if (index == str.size())return 1;if (str[index] == '0')return 0;else{if (str[index] != '*'){ans = dfs(index + 1, str);if (index + 1 < str.size() && str[index + 1] != '*'){if (index + 1 < str.size() && (str[index] - '0') * 10 + str[index + 1] - '0' <= 26){ans += dfs(index + 2, str);}}else if (index + 1 < str.size() && str[index + 1] == '*'){if (str[index] == '1') ans += dfs(index + 2, str) * 9;else if (str[index] == '2') ans += dfs(index + 2, str) * 6;}}else if (str[index] == '*'){ans = 9 * dfs(index + 1, str);if (index + 1 < str.size()){if (str[index + 1] == '*'){ans += dfs(index + 2, str) * 15;}else if (str[index + 1] != '*'){if (str[index + 1] <= '6') ans += dfs(index+2,str) * 2;else ans += dfs(index + 2, str) * 1;}}}}return ans%mod;
}int main()
{string str = "7*9*3*6*3*0*5*4*9*7*3*7*1*8*3*2*0*0*6*";cout << dfs(0, str) << endl << endl;int n = str.size();vector<long long>dp(n + 1);dp[n] = 1;for (int index = n - 1; index >= 0; index--){if (str[index] != '0'){if (str[index] != '*'){dp[index] = dp[index + 1];if (index + 1 < str.size() && str[index + 1] != '*'){if (index + 1 < str.size() && (str[index] - '0') * 10 + str[index + 1] - '0' <= 26){dp[index] += dp[index + 2];}}else if (index + 1 < str.size() && str[index + 1] == '*'){if (str[index] == '1') dp[index] += dp[index + 2] * 9;else if (str[index] == '2') dp[index] += dp[index + 2] * 6;}}else if (str[index] == '*'){dp[index] = 9 * dp[index + 1];if (index + 1 < str.size()){if (str[index + 1] == '*'){dp[index] += dp[index + 2] * 15;}else if (str[index + 1] != '*'){if (str[index + 1] <= '6') dp[index] += dp[index + 2] * 2;else dp[index] += dp[index + 2] * 1;}}}}dp[index] %= mod;}for (auto i : dp)cout << (int)i << " ";return 0;
}力扣字符串环绕
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<string>
#include<map>
using namespace std;void dp1(string str) //我的写法错误
{map<char, int>ma;for (int i = 0; i < str.size(); i++){if (str[i] == 'a' && i > 0 && str[i - 1] == 'z'){ma['a'] = ma['z'] + 1;}else if (i > 0 && str[i - 1] == str[i] - 1){ma[str[i]] = ma[str[i - 1]] + 1;}elsema[str[i]] = max(ma[str[i]], 1);}int ans = 0;for (auto i : ma){ans += i.second;cout << i.first << "-" << i.second << " ";}cout << endl;cout << ans << endl << endl << endl;}void dp2(string str) //纠正
{map<char, int>ma;int len = 0;for (int i = 0; i < str.size(); i++){if (i > 0 && (str[i] == 'a' && str[i - 1] == 'z' || str[i - 1] == str[i] - 1)){len++;}elselen = 1;ma[str[i]] = max(ma[str[i]], len);}int ans = 0;for (auto i : ma){ans += i.second;cout << i.first << "-" << i.second << " ";}cout << endl;cout << ans << endl << endl << endl;}int main()
{string str("abcdefghijklmnopqrstuvwxymnopqrstuvwxyz");cout << str << endl << endl;dp1(str);dp2(str);return 0;
}
