(子序列计数dp)1955. 统计特殊子序列的数目

1955. 统计特殊子序列的数目

子序列计数问题，应该是通过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;
    }
};