做网站快速排名,甘肃省建设工程造价信息网站,网站是什么公司做的,邯郸网页题干:力扣 解题报告#xff1a;
刚开始觉得直接贪心选有短则短#xff0c;但是发现不行#xff0c;不能贪心有短的可以操作的则选短的。 三个方式想到倒着递推。一是直接记住这个特例#xff0c;正推还倒推不能互相转换的特例。
二是因为dp[i]代表前i个的最大次数#x…题干:力扣 解题报告
刚开始觉得直接贪心选有短则短但是发现不行不能贪心有短的可以操作的则选短的。 三个方式想到倒着递推。一是直接记住这个特例正推还倒推不能互相转换的特例。
二是因为dp[i]代表前i个的最大次数这其实不只要保存最大次数这一个状态还有可能很多局部最优解需要保存。怎么消除这个因素呢就是怎么让他和子状态无关呢倒着推结合这题的题意正好。
三是正难则反的思想。正着想是dp[i]代表前i个能消除的最大次数枚举最后一次消除次数反着想就是dp[i]代表从i到结尾都消除的最大次数然后枚举第一次消除的字符串。然后一想诶这就是可解的了。
然后就是对于如何判断两个字符串的相等可以字符串哈希也可以用求LCP的板子。
AC代码
class Solution {
public:unsigned long long H[5005];unsigned long long p[5005];// 都自然溢出即可int seed 31, dp[5005];bool ok[5005][5005];unsigned long long cal(int l, int r) {if (l 0) return H[r];return H[r] - H[l-1] * p[r-l1];}int deleteString(string s) {H[0] s[0]-a1;p[0] 1;for(int i 1; is.size(); i) p[i] p[i-1]*seed;for(int i 1; is.size(); i) {H[i] H[i-1]*seed s[i] - a 1;}int ans 0;int st 0;for(int i 0; is.size(); i) {for(int j i1; js.size(); j2) {int len j-i1;if(cal(i, ilen/2-1) cal(ilen/2, ilen-1)) ok[i][j] 1;}}for(int i s.size()-1; i0; i--) {dp[i] 1;for(int j i1; js.size(); j2) {if(ok[i][j]) dp[i] max(dp[i], dp[i(j-i1)/2] 1);}}return dp[0];}
}; 错误代码从前往后递推的
class Solution {
public:unsigned long long H[5005];unsigned long long p[5005];// 都自然溢出即可int seed 31, dp[5005];bool ok[5005][5005];unsigned long long cal(int l, int r) {if (l 0) return H[r];return H[r] - H[l-1] * p[r-l1];}int deleteString(string s) {H[0] s[0]-a1;p[0] 1;for(int i 1; is.size(); i) p[i] p[i-1]*seed;for(int i 1; is.size(); i) {H[i] H[i-1]*seed s[i] - a 1;}int ans 0;int st 0;for(int i 0; is.size(); i) {for(int j i1; js.size(); j2) {int len j-i1;if(cal(i, ilen/2-1) cal(ilen/2, ilen-1)) ok[i][j] 1;}}for(int i 0; is.size(); i) {dp[i] -1;if(ok[0][i]) dp[i] 1;for(int j 1; ji; j) {if(ii-j s.size()) continue;if(dp[j] ! -1 ok[j1][ii-j]) {dp[i] max(dp[i], dp[j]1);}}if(i ! s.size()-1) ans max(ans, dp[i]);}return max(ans1, dp[s.size()-1]);}
}; LCP
lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀 n len(s)lcp [[0] * (n 1) for _ in range(n 1)] # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀for i in range(n - 1, -1, -1):for j in range(n - 1, i, -1):if s[i] s[j]:lcp[i][j] lcp[i 1][j 1] 1
