【算法学习笔记】29：动态规划中可丢弃状态的维度压缩

状态表示：$f(i,j)$

• 集合：对于$\mathrm{0..}i$组成的子数组，$j=0$时表示全0，$j=1$时表示正整数个0后接正整数个1，$j=2$时表示正整数个0后接正整数个1后接正整数个2，如此子序列组成的集合
• 属性：Count（集合中元素的数量）

记$x$为$nums[i]$，则有状态转移：

• 当$x=0$，$f(i,0)=2\ast f(i-1,0)+1$，这个$2\ast$表示$i$位置的元素选或者不选，$+1$表示这个$i$位置的新的$0$自己组成的新的子序列
• 当$x>0$，$f(i,x)=2\ast f(i-1,x)+f(i-1,x-1)$
• 对于$y\in [\mathrm{0..2}]|y\ne x$，$f(i,y)=f(i-1,y)$

初始时，$f(0,>0)=0$，如果首个元素是$0$那么$f(0,0)=1$，否则$f(0,0)=0$

class Solution {
public:int countSpecialSubsequences(vector<int>& nums) {constexpr int mod = 1e9 + 7;int n = nums.size();vector<vector<int>> f(n, vector<int>(3, 0));if (0 == nums[0]) f[0][0] = 1;for (int i = 1; i < n; i ++ ){for (int j = 0; j < 3; j ++ )f[i][j] = f[i - 1][j];if (0 == nums[i])f[i][0] = ((2 * f[i - 1][0]) % mod + 1) % mod;elsef[i][nums[i]] = ((2 * f[i - 1][nums[i]]) % mod + f[i - 1][nums[i] - 1]) % mod;}return f[n - 1][2];}
};

这里用了二维数组来存每个状态，但注意到$i$只依赖$i-1$进行状态转移，并且返回的也是$n-1$时的结果，所以$i-1$是一个可丢弃状态，因此可以进行空间压缩，直接把$i$这个维度去掉即可：

class Solution {
public:int countSpecialSubsequences(vector<int>& nums) {constexpr int mod = 1e9 + 7;int n = nums.size();int f[3] = {nums[0] ? 0 : 1, 0, 0};for (int i = 1; i < n; i ++ ){if (0 == nums[i])f[0] = ((2 * f[0]) % mod + 1) % mod;elsef[nums[i]] = ((2 * f[nums[i]]) % mod + f[nums[i] - 1]) % mod;}return f[2];}
};