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]!=0
ans = 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;
}
else
ma[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++;
}
else
len = 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;
}