开发者社区> 问答> 正文

不懂就问,算法问题,萌新提问

1)第一行输入字符串 A, 第二行输入字符串 B
数据规模:len(B)2)计算在 A 的中子序列 B 出现的次数
样例:输入abcacca ac 输出:5

很明显的动态规划问题,,,可是这个数据规模a和b小于20万,数组开这么大的实属扯,所以求大佬们想想怎么解决。。。

我的代码:

include

include

using namespace std;
static int dp200000;
int numDistinct(string S, string T)
{

if (S.empty() || T.empty()) return 0;
if (S.length()<T.length()) return 0;
dp[0][0] = 1;
for (int i = 1; i <= T.length(); i++) {
    dp[i][0] = 0;
}
for (int j = 1; j <= S.length(); j++) {
    dp[0][j] = 1;
}
for (int i = 1; i <= T.length(); i++) {
    for (int j = 1; j <= S.length(); j++) {
        dp[i][j] = dp[i][j - 1];
        if (T[i - 1] == S[j - 1])
            dp[i][j] += dp[i - 1][j - 1];
    }
}
return dp[T.length()][S.length()];

}
int main(void)
{

string S, T;
cin >> S >> T;
cout << numDistinct(S, T) << endl;
return 0;

}

acm平台提示运行错误(数组越界)

展开
收起
tim33470348 2018-11-23 14:04:32 4034 0
3 条回答
写回答
取消 提交回答
  • 利用“滚动数组”来做,其实有更利于理解的做法。 你会发现,对于ai来说,ansbj会从ansb(j-1)进行一轮继承,所以在每个i上,new一个新的数组,进行继承,然后free掉之前的数组就可以了 不同于滚动数组,这个方法其实只是将一开始申请的超额内存动态申请

    2019-09-07 23:32:39
    赞同 展开评论 打赏
  • 你发现你的dp转移方程,只依赖于上一行的数据,这时候你就可以用滚动数组把空间复杂度降下来了

    2019-07-17 23:16:11
    赞同 展开评论 打赏
  • 知乎SimonS

    你在计算dpi的时候,只需要依赖i-1那行的数据,所以可以使用滚动数组,把空间复杂度O(ST)降为线性。

    2019-07-17 23:16:11
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
超全算法笔试 模拟题精解合集 立即下载
超全算法笔试-模拟题精解合集 立即下载
大模型时代的搜推广应用和实践 立即下载