| ２０２０／７／２ | 要点 |
|---|---|
| 普通ｄｐ | 两个字符串的匹配，一个字符串可以添删改其中的字符，求变成另一个字符串的最少操作步数，ｄｐ［ｉ］［ｊ］表示分别到ｉ和ｊ位置的最少步数，这样状态无后效性 |
| 模拟题 | 字符串模拟，用python方便很多， ｏｒｄ和ｃｈｒ两个函数，利用 map(int,input().strip().split())输入, |
| 水题 | 字符串模拟,python:a[::-1]实现字符串reverse |
| ２０２０／７／3 | 要点 |
|---|---|
| 水题 | 对于int,ceil(n/2.0)和(n+1)/2 不一样?不一样,前者输出时doubel,后者时int,例如对于n=493796142,2.46898e+008和246898071 |
| 水题 | 看清题意即为等差数列+特判 |
| 水题 | 无 |
时间好快呀，一晃过去六天没写题
| 2020/7/9 | 要点 |
|---|---|
| 模拟题 | 利用递归或者栈做字符串解压模拟，从外到里，一层层去掉括号，可以保证顺序不变 |
| 贪心 | 开始以为是个dp，发现复杂度过不去。注意枚举顺序，利用有限队列维护。priority_queue<ll,vector<ll>,greater<ll> >是小顶堆 |
| 区间dp | 1.区间dp的特点是，区间长度较小，而且一般状态三四个维度，最外层枚举区间长度，第二层确定起点 |
| 区间dp | 求最长回文子序列，\(dp[i][j]\) 为字符串s 的第 i 个字符到第 j个字符的最长回文子序列长度。状态转移：\(if: s[i]==s[j],dp[i][j]=dp[i+1][j-1]+2. else:dp[i][j]=max(dp[i+1][j],max[i][j-1]\) |
| 区间dp | 求最长回文子串，我们可以强行规定\(dp[i][j]\) s中第 i 个字符和第 j 个字符都必须选，换句话说 \(dp[i][j]\) 其实是选完了整个 i 到 j 的区间的，也就是说，\(dp[i][j]==j-i+1\)时，这个区间是个回文串，否则就不是,\(dp[i][j]=0\) ,所以只需要用0，1表示是否是回文串。状态转移：\(if :dp[i+1][j-1]==1 ,and ,s[i]==s[j]时,dp[i][j]=1,else :dp[i][j]=0\)。 |
| 区间dp | 利用两个字符串，组拼成为一个字符串，只需要保持原来每个字符串的字符相对位置不变即可，与上一个类似，\(dp[i][j][k][l]\)表示选择第一个字符串i到j的位置，第二个字符串k到l的位置，是否组成回文串，四个状态注意。 |
题意：将n个石子分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。
把n划分为k个，那么先从n中拿一个x，题目便变为将(n-x)分为k-1种，所以我们可以依次拿一个1出来，递推式为\(f[i?1][j?1]\)，即有1的情况；
没有1的情况，可以看成为j个元素预分配一个1，剩下的便没有1，即f[i-j][j]f[i?j][j]。故当i>ji>j时便有了递推式\(f[i][j]=f[i-1][j-1]+f[i-j][j]\)
超时dfs,保存每一种方案
void dfs(int num,int cur,int big){
if(cur==1){
v.push_back(num);
v_copy.assign(v.begin(),v.end());
sort(v_copy.begin(),v_copy.end());
se.insert(v_copy);
v.pop_back();
return;
}
for(int i=big;i<=num-cur+1;i++){
v.push_back(i);
dfs(num-i,cur-1,big);
v.pop_back();
}
}
不超时dfs：
int dfs(int num,int cur){
if(num<cur)return 0;
if(cur==1)return 1;
return dfs(num-1,cur-1)+dfs(num-cur,cur);
}
原文：https://www.cnblogs.com/gzr2018/p/13302336.html