本题中不同特殊子序列其实就是组成子序列(不一定要连续的)，只不过这题还加入了限制，就是子序列必定满足0,1,2这个顺序的而已。
那么这题我们先想一个暴力解法，就是怎么样才能把所有序列都统计进去，其实在考虑这道题的暴力解法之前，我们把他看做一个不用满足0,1,2这个顺序的序列，随便组的话，是不是n^3了，从一个作为为起始点地方延伸出去的情况下。这个时候我们再考虑下以一个下标为结尾的话能不能优化出来，发现前一个下标状态的方案数可以转移到当前下标的状态的方案数，是有一个规律，比如1 2 3，第四个数是4，前三个的方案数是6，那么转移到第四个的话，总共方案数是多少呢？以第一个数为结尾的方案数有1，前二个数结尾的方案数等于以第一个结尾的方案数加上以第二个为结尾的方案数1 + 1 + 1等于3，前三个为结尾的有3 + 3等于6。那么本题中就多了一个条件就是一定要是0,1,2序列才行，那么我们转移时是0，1，2的时候判断一下就行了，比如当前位是1，那么只能从前面结尾是0的序列，和前面有个结尾是1的序列转移过来，两个相加
f[i][1] = f[i – 1][0] + f[i – 1][1] + f[i – 1][1];同理当前位是2也是，同理当前位为1也是，但是这里还有一个很重要的点就是，这个数是0的时候，其他的状态怎么办呢？f[i][1],f[i][2]这个状态怎么办呢？
这个我们就之前转移前面的，因为我们在转移的时候，只要知道当前位之前的序列方案数就行，那么这样其实我们就可以优化了，只用三个数就可以知道了，一个数保存前i个状态的0序列总的方案个数，同理，这里我就不优化了
class Solution {
public:
const int MOD = 1e9+7;
int countSpecialSubsequences(vector<int>& nums)
{
int f[110000][3];
memset(f,0,sizeof(f));
int s[110000][3];
vector<int> a(nums.size() + 10);
for(int i = 0;i < nums.size();i++) a[i + 1] = nums[i];
for(int i = 1;i <= nums.size();i++)
{
if(a[i] == 0)
{
f[i][0] = (f[i - 1][0] + (f[i - 1][0] + 1)%MOD)%MOD;
f[i][1] = f[i - 1][1];
f[i][2] = f[i - 1][2];
}
if(a[i] == 1)
{
f[i][1] = (f[i - 1][1] + (f[i - 1][1] + f[i - 1][0])%MOD)%MOD;
f[i][0] = f[i - 1][0];
f[i][2] = f[i - 1][2];
}
if(a[i] == 2)
{
f[i][2] = (f[i - 1][2] + (f[i - 1][2] + f[i - 1][1])%MOD)%MOD;
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1];
}
//cout<<f[i][0]<<" "<<f[i][1]<<" "<<f[i][2]<<endl;
}
return f[nums.size()][2];
}
};原文地址:https://blog.csdn.net/txh1873749380/article/details/135839613
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_62325.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
