题解 | #平衡的选择题#

题意整理

• 牛牛准备出一套卷子，共n个多项选择题。
• 正确答案中，A和C出现次数差距不超过1，B和D出现次数差距不超过2。
• 问有多少种符合要求的正确答案。

方法一（动态规划）

1.解题思路

正确答案主要由两个因素决定它的种类数，一是A和C出现次数差距，二是B和D出现次数差距，可以通过这两个因素确定15种状态，每种状态的方案数累加，即是正确答案的数量。

A和C出现次数差距可以是-1，0，1，B和D出现次数差距可以是-2，-1，0，1，2，将参数对齐到大于等于0之后，分别对应j=0,1,2以及k=0,1,2,3,4

mask从1到15分别对应15种答案，其对应关系如下表所示:

• 状态定义：中i表示题目数量，j表示A、C出现次数差值，k表示B、D出现次数差值，表示对应状态的方案数。
• 状态初始化：当题目只有一个时，初始化每种方案的数量。
• 状态转移：每增加一个题目，对应的A、C出现次数差值和B、D出现次数差值就可能发生变化，根据mask对应的15种答案，如果j、k变化后仍然在平衡范围内，则跟新对应的状态，即。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;

    public int solve (int n) {
        //初始化dp数组,dp[i][j][k]中i表示题目数量，j表示A、C出现次数差值，k表示B、D出现次数差值
        int[][][] dp=new int[n+1][3][5];
        //只有一个题目时的情况
        for(int mask=1;mask<=15;mask++){
            //mask为对应的15种答案，A、B、C、D分别表示每个答案中对应A、B、C、D出现次数
            int A=(mask>>3)&1,B=(mask>>2)&1,C=(mask>>1)&1,D=mask&1;
            dp[1][1+A-C][2+B-D]++;
        }

        for(int i=2;i<=n;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<5;k++){
                    for(int mask=1;mask<=15;mask++){
                        int A=(mask>>3)&1,B=(mask>>2)&1,C=(mask>>1)&1,D=mask&1;
                        //如果加上一题后，对应差值仍在平衡范围内，则跟新状态
                        if(j+A-C>=0&&j+A-C<3&&k+B-D>=0&&k+B-D<5){
                            dp[i][j+A-C][k+B-D]=(dp[i][j+A-C][k+B-D]+dp[i-1][j][k])%mod;
                        }
                    }
                }
            }
        }

        int res=0;
        //将每种状态对应的方案数累加
        for(int j=0;j<3;j++){
            for(int k=0;k<5;k++){
                res=(res+dp[n][j][k])%mod;
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：循环体最多执行次，所以时间复杂度是。
• 空间复杂度：需要额外大小为的dp数组，所以空间复杂度是。

方法二（空间压缩）

1.解题思路

由于方法一中，每增加一题之后的状态只与对应的未增加这一题时的状态有关，所以可以通过滚动数组的方式压缩空间，dp[0][j][k]表示未增加某一题时的状态，dp[1][j][k]表示增加这一题之后的状态。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    //初始化取余常数
    int mod=1000000007;

    public int solve (int n) {
        //初始化dp数组,dp[i][j][k]中i表示滚动数组变量，j表示A、C出现次数差值，k表示B、D出现次数差值
        int[][][] dp=new int[2][3][5];

        //给dp[0][j][k]赋初值
        for(int mask=1;mask<=15;mask++){
            //mask为对应的15种答案，A、B、C、D分别表示每个答案中对应A、B、C、D出现次数
            int A=(mask>>3)&1,B=(mask>>2)&1,C=(mask>>1)&1,D=mask&1;
            //A-C范围在[-1,1]，B-D范围在[-2,2]，由于下标从0开始，每个状态需要加常数进行对齐
            dp[0][1+A-C][2+B-D]++;
        }

        for(int i=1;i<n;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<5;k++){
                    for(int mask=1;mask<=15;mask++){
                        int A=(mask>>3)&1,B=(mask>>2)&1,C=(mask>>1)&1,D=mask&1;
                        //如果加上一题后，对应差值仍在平衡范围内，则跟新状态
                        if(j+A-C>=0&&j+A-C<3&&k+B-D>=0&&k+B-D<5){
                            dp[1][j+A-C][k+B-D]=(dp[1][j+A-C][k+B-D]+dp[0][j][k])%mod;
                        }
                    }
                }
            }
            //跟新完状态后，将i为1的dp数组赋值给i为0的dp数组，初始化i为1的dp数组，为下次跟新状态做准备
            System.out.println();
            for(int j=0;j<3;j++){
                for(int k=0;k<5;k++){
                    dp[0][j][k]=dp[1][j][k];
                    dp[1][j][k]=0;
                }
            }
        }

        int res=0;
        //将每种状态对应的方案数累加
        for(int j=0;j<3;j++){
            for(int k=0;k<5;k++){
                res=(res+dp[0][j][k])%mod;
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：循环体最多执行次，所以时间复杂度是。
• 空间复杂度：需要额外大小为常数级别的dp数组，所以空间复杂度是。