首页 > 代码库 > 第七周 Leetcode 466. Count The Repetitions 倍增DP (HARD)
第七周 Leetcode 466. Count The Repetitions 倍增DP (HARD)
Leetcode 466
直接给出DP方程
dp[i][k]=dp[i][k-1]+dp[(i+dp[i][k-1])%len1][k-1];
dp[i][k]表示从字符串s1的第k位开始匹配2^k个s2串需要的长度
最后通过一个循环 累积最多可以匹配多少个s2串 除以n2下取整就是答案
用倍增加速后 总的复杂度nlogn 而本题的n非常小 轻松AC
体会到倍增的魅力了吧。
const int maxn=100+1,INF=1e+9;
long long int dp[maxn][30];
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
memset(dp,0,sizeof(dp));
int len1=s1.length(),len2=s2.length();
int l1=0,l2=0;
for(int i=0;i<len1;i++)
{
l1=i;l2=0;
while(l2<len2)
{
while(l1<n1*len1&&s1[l1%len1]!=s2[l2])l1++;
l1++;l2++;
}
dp[i][0]=l1-i;
}
for(int k=1;k<30;k++)
for(int i=0;i<len1;i++)
{
dp[i][k]=dp[i][k-1]+dp[(i+dp[i][k-1])%len1][k-1];
}
long long int ans=0;
int begin=0;
for(int k=29;k>=0;k--)
while((begin+dp[(begin%len1)][k])<=n1*len1)
{ans+=(1<<k);begin+=dp[(begin%len1)][k];}
return ans/n2;
}
};
第七周 Leetcode 466. Count The Repetitions 倍增DP (HARD)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。