leetcode日记(99)不同的子序列
挺难的TT一开始居然把动态规划转移方程写错了,导致后面怎么改都通不过……
找转移方程真是件难事啊……
方法是照常建立动态规划数组,nums[i][j]代表s的前i含多少个t的前j,这个比较容易想。
转移方程还是有点难度的,每次遍历一个t[j]就有两种情况,一种是t[j]和s[i]相同,一种是不同,而相同又有两种情况,一种是匹配一种是跳过t[j]不匹配,如果跳过那就和t[j]不等于s[j]一样,直接就取nums[i][j-1],如果匹配那就是nums[i-1][j-1],所以t[j]和s[i]相同的情况下nums[i][j]=nums[i-1][j-1]+nums[i][j-1]。
一开始想的太复杂了,其实只要从最简单的i为0起手就行,i为0时任何j都能匹配所以一整行都是1,然后慢慢往下循环。
这是第一版代码:
class Solution {
public:
unsigned long int nums[1001][1001];
int numDistinct(string s, string t) {
memset(nums,0,sizeof(nums));
for(int i=0;i<=s.size();i++) nums[i][0]=1;
for(int i=1;i<=s.size();i++){
for(int j=1;j<=t.size();j++){
if(s[i-1]==t[j-1]) nums[i][j]=nums[i-1][j-1]+nums[i-1][j];
else nums[i][j]=nums[i-1][j];
}
}
return nums[s.size()][t.size()];
}
};
消耗内存还是太多了,其实想到可以简化空间复杂度,只需要一个一维数组记录就行,若不相等则不变,若相等则加上前一个数。
class Solution {
public:
unsigned long int nums[1001];
int numDistinct(string s, string t) {
memset(nums,0,sizeof(nums));
nums[0]=1;
for(int i=1;i<=s.size();i++){
for(int j=t.size();j>=1;j--){
if(s[i-1]==t[j-1]) nums[j]=nums[j-1]+nums[j];
}
}
return nums[t.size()];
}
};
简化了很多,需要注意t要从后往前匹配,因为不能影响到后面的数值。