题解 | #消息压缩#

题意

给定正整数数N，求把N分割成一些正整数a₁,a₂......a_k的方案总数，其中k是偶数且a_2i-1=4

30分做法：暴力搜索

class Solution {
public:
    const int MOD=998244353;
    int messageCount(int N) {
        return dfs(N);
    }
    int dfs(int t)
        {
            int ans=0;//初始化答案
            if(t==0) return 1;//若分割成功答案+1
            if(t<=4) return 0;//若分割不成功答案不变
            for(int i=1;i<=t-4;++i) {ans+=dfs(t-4-i);ans%=MOD;}//递归计算答案
        return ans;
        }
};//时间复杂度O(N!)

直接深度搜索每一种方案并返回总方案数，若分割成功，将方案数加1，最后计算总方案数。
时间复杂度： $O(N!)$ ，当dfs到第N层时，需要再次dfs从N-4到1，故时间复杂度为 $O(N!)$ 。
空间复杂度： $O(N)$ ,每次dfs所用栈空间为 $O(N)$ 级别。

60分做法：记忆化搜索

class Solution {
public:
    const int MOD=998244353;
    int a[1000005];
    int messageCount(int N) {
        memset(a,0,sizeof a);
        return dfs(N);
    }
    int dfs(int t)
        {
        if(a[t]) return a[t];//如果已经搜索过了直接返回，避免重复搜索
             int ans=0;//初始化答案
            if(t==0) return 1;//若分割成功答案+1
            if(t<=4) return 0;//若分割不成功答案不变
            for(int i=1;i<=t-4;++i) {if(!a[t-4-i])a[t-4-i]=dfs(t-4-i);ans+=a[t-4-i];ans%=MOD;}//存储已经计算的答案
        return ans;
        }
};//时间复杂度O(N^2)

a数组用于储存已经计算的dfs函数，节省了大量时间，但搜索仍不是正解
时间复杂度： $O(N^2)$ ，对于每个N只会进行一次搜索，每个N平均搜索N/4次，时间复杂度约为平方级别。
空间复杂度： $O(N^2)$ ，从1到n每个数都跑一次dfs，每次dfs复杂度约为 $O(N)$ ，故空间复杂度为 $O(N^2)$

100分做法：动态规划

class Solution {
public:
    const int MOD=998244353;
    int messageCount(int N) {
        int dp[1000005];
        memset(dp,0,sizeof dp);
        dp[5]=1;
        for(int i=6;i<=N;i++)
            dp[i]=(dp[i-1]+dp[i-5])%MOD;
        return dp[N];
    }
};//时间复杂度O(N)

本题的正解应当为动态规划。观察到后面数字的变化不影响之前数字的规律成立，考虑动态规划。
假设 $dp[N]$ 指消息长度为N时的划分数，容易知道 $图片说明$ 。下面证明一下该递推公式：
对于消息长度为N-1的情况，在划分出的数中最后一个数加1（例如4 1 4 2->4 1 4 3），仍是一个合法数列，对于消息长度为N-5的情况，在划分出的数中加入4,1两个数，也仍是一个合法数列（例如4 1 4 2->4 1 4 2 4 1），前者遍历了所有最后一个数大于1的方案，后者遍历了所有最后一个数为1的方案，两者合起来就是指消息长度为N时的划分数。

而当N=5时，方案只有一种，故可以从一直推算出 $图片说明$ 。代码中只有一个循环，时间复杂度为 $图片说明$ 。
空间复杂度： $O(N)$ ,为 $dp[n]$ 数组的空间开销。

图为已知 $dp[6]$ 与 $dp[10]$ 计算 $dp[11]$ 的过程，可以看到 $A$ 是由 $a$ 经过末尾加入4,1变成的， $B$ 与 $C$ 是 $b$ 与 $c$ 经过最后一个数字加1得来的。