子序列计数问题，应该是通过dp解决（考虑状态转移方程）
class Solution {
public:
int countSpecialSubsequences(vector<int> &nums) {
int n = nums.size();
int f0 = 0, f1 = 0, f2 = 0;
const int MOD = 1e9 + 7;
for (int i = 0; i < n; i++) {
if (nums[i] == 0) f0 = (f0 * 2 % MOD + 1) % MOD;
if (nums[i] == 1) f1 = (f1 * 2 % MOD + f0) % MOD;
if (nums[i] == 2) f2 = (f2 * 2 % MOD + f1) % MOD;
}
return f2 % MOD;
}
};
1955. 统计特殊子序列的数目[https://leetcode-cn.com/problems/count-n...
DP(最长公共子序列)
（简单dp？？？excuse？？） dp：最大不连续子序列和
1143. 最长公共子序列 相关标签： DP 5. 最长回文子串 相关标签 ：DP
最长公共子串 子串的要求比子序列严格，所以可以讨论子串的终点 最长公共子序列 DP解 递归+memo 最长公共回文...
DP问题求解之连续子序列 continous subarrays类型问题是求数组中连续子序列是否满足某些条件的类型...
一些子序列问题 （持续补充） 最长上升子序列 题目 dp数组，每一个数组记录前面最长的上升序列长度。 和标程对比 ...
每一个数之前的上升序列个数dp[i]：以ai为末尾的最长上升子序列的长度以ai结尾的上升子序列是：只包含ai的子序...
区间dp降低时间复杂度 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩...
简单题 696. 计数二进制子串: 一次遍历字符串2020.08.12 连续子序列 vs 子序列 x有序连续思路1...
本文标题：(子序列计数dp)1955. 统计特殊子序列的数目
本文链接：https://www.haomeiwen.com/subject/dcodvltx.html
网友评论