首页 > 代码库 > Distinct Subsequences [leetcode] DP,空间复杂度O(T.size)
Distinct Subsequences [leetcode] DP,空间复杂度O(T.size)
求S中和T相同的子串的个数。
递推公式:
dp(i,j):S[0...i-1]和T[0...j-1]中不同子串的个数。
dp(0,j) = 0
dp(i,0) = 1
一般情况下
dp(i,j) = dp(i-1,j-1) + dp(i-1,j) S[i-1] == T[j-1],保留S[i-1]以及丢弃S[i-1]
= dp(i-1,j) S[i-1] != T[j-1],丢弃S[i-1],只比较S[0...j-2]和T[0...i-1]
因为dp(i,j)仅仅与dp(i-1,?)有关,所以可以将空间降维至一维
因为dp(i,j)计算时会用到dp(i-1, j)和dp(i-1,j-1)所以降维后新的dp(j)在计算时会用到旧的dp(j)和dp(j-1),因此在计算时应该从j=T.size()-1开始,从后往前计算。
dp(0) = 1
dp(j) = dp(j) + dp(j-1) S[i-1] == T[j-1],保留S[i-1]以及丢弃S[i-1]
dp(j) S[i-1] != T[j-1],丢弃S[i-1]
代码如下:
int numDistinct(string S, string T) { if (S.size() == 0 || T.size() == 0) return 0; vector<int> dp(T.size() + 1); dp[0] = 1; for (int i = 1; i <= S.size(); i++) for (int j = T.size() ; j >= 0; j--) if (S[i - 1] == T[j - 1]) dp[j] += dp[j - 1]; return dp[T.size()]; }
Distinct Subsequences [leetcode] DP,空间复杂度O(T.size)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。