题解 | #平衡的选择题#

思路：

题目的主要信息：

选择题答案有15种情况：A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCDA,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD
对于每道题 $i$ ，要使前 $i$ 道题，A与C的相差不超过1，B与D想抄不超过2
问总共有多少种答案布局方式，结果需取模1e9+7

方法一：动态规划
具体做法：
我们给每个答案编号为0-14（对应上述15种情况），用 $dp[i][j]$ 表示前 $i$ 道题以编号 $j$ 结尾的题目的方案种类有多少。对于15种情况，我们遍历 $i-1$ 的15种情况，，一一比较，可以事先算出AC的差值和BD的差值，如果符合条件则将 $i-1$ 的对应的加入 $i$ 中。
因为上述我们只用到了 $i$ 和 $i-1$ ，因此我们可以使用两个一维数组滚动模拟二维数组，省去了不少空间。

class Solution {
public:
    int solve(int n) {
        int mod = 1e9 + 7;
        vector<int> dp(15, 0); //分别对应15种答案，以该答案结尾的方案数
        dp[7] = 1; //初始
        vector<int> temp(15);
        for(int i = 0; i < n; i++){
            for(int k = 0; k < 15; k++){ //数组滚动，省空间
                temp[k] = dp[k];
                dp[k] = 0;
            }
            for(int x = 1; x <= 15; x++){ //i的15种情况
                int AC = ((x >> 0) & 1) - ((x >> 1) & 1); //比较AC的差
                int BD = ((x >> 2) & 1) - ((x >> 3) & 1); //比较BD的差
                for(int s = 0; s < 15; s++){  //i-1的15种情况
                    int i = s / 5, j = s % 5;
                    if(i - AC >= 0 && i - AC < 3 && j - BD >= 0 && j - BD < 5)
                        dp[s] = (dp[s] + temp[(i - AC) * 5 + (j - BD)]) % mod;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < 15; i++) //15种情况相加
            res = (res + dp[i]) % mod;
        return res;
    }
};

复杂度分析：

时间复杂度： $O(15^2*n)=O(n)$ ，外循环遍历到 $n$ ，内循环两层都是15
空间复杂度： $O(1)$ ，两个辅助数组都是常数空间

方法二：分类讨论法
具体做法：
方法一是对每种结尾分开讨论，其实我们可以将其分类，如果我们把状态数分为6种，其中初始状态如下有4种：
图片说明
这6种结尾都是符合要求的，我们就把种类从15缩小到了6.然后对于每一种情况，我们用 $dp[i][j]$ 表示前 $i$ 道题，最后是情况 $j$ 。假如 $j=0$ ，我们可以有：

对于 $i-1$ 的情况0，再次加上情况的三种情况依然平衡，于是有 $3*dp[i-1][0]$
对于 $i-1$ 的情况1，如果是A可以选择C或者CBD，如果是ABD可以选择C或者CBD，如果是C可以选择A或者ABD，如果是CBD可以选择A或者ABD来保持平衡，消除AC之间的差值，于是每个都有2种选择，有 $2*dp[i-1][1]$
对于 $i-1$ 的情况2，如果是B可以选择B或者ACD，如果是ACB可以选择D或者ACD，如果是D可以选择B或者ACB，如果是ACD可以选择B或者ACB来保持平衡，消除BD之间的差值，于是每个都有2种选择，有 $2*dp[i-1][2]$
对于 $i-1$ 的情况3，每种有一个选择使自己平衡，有 $dp[i-1][3]$

对于 $i-1$ 的情况4和5，无论怎么选都不能平衡
因此我们的 $dp[i][0]$ 只需要将上述情况相加即可。其他情况的推理类似，不再赘述。
同时，为了节省空间，我们依旧使用两个一维数组滚动。

class Solution {
public:
  int solve(int n) {
      int mod = 1e9 + 7;
      vector<long long> dp(6);
      vector<long long> temp(6);//dp和tamp都表示i道题时，该情况下的方法数
      dp[0] = 3, dp[1] = 4, dp[2] = 4, dp[3] = 4, dp[4] = 0, dp[5] = 0; //初始情况，1道题时
      for(int  i = 1; i < n; i++){
          temp[0] = (3 * dp[0] + 2 * dp[1] + 2 * dp[2] + dp[3]) % mod;
          temp[1] = (4 * dp[0] + 3 * dp[1] + 2 * dp[2] + 2 * dp[3]) % mod;
          temp[2] = (4 * dp[0] + 2 * dp[1] + 3 * dp[2] + 2 * dp[3] + 2 * dp[4] + dp[5]) % mod;
          temp[3] = (4 * dp[0] + 4 * dp[1] + 4 * dp[2] + 3 * dp[3] + 2 * dp[4] + 2 * dp[5]) % mod;
          temp[4] = (2 * dp[2] + dp[3] + 3 * dp[4] + 2 * dp[5]) % mod;
          temp[5] = (2 * dp[2] + 2 * dp[3] + 4 * dp[4] + 3 * dp[5]) % mod;
          //数组滚动，省空间
          dp[0] = temp[0];
          dp[1] = temp[1];
          dp[2] = temp[2];
          dp[3] = temp[3];
          dp[4] = temp[4];
          dp[5] = temp[5];
      }
      int res = 0;
      for(int i = 0; i < 6; i++) //所有情况相加
          res = (res + dp[i]) % mod;
      return res;
  }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次到 $n$ 的遍历
空间复杂度： $O(1)$ ，数组是常数空间