题解 | #消息压缩#

题意整理

有一段长度为n的消息，要将消息分成若干组，每组2个消息。
第一个消息长度必须是4，第二个消息长度不能为0。
求有多少种分割方法。

方法一（递归）

1.解题思路

递归终止条件：如果剩下的长度为0，说明正好完成分割，返回一种方案。
递归如何推进：首先减去4，表示第一个消息的长度，然后第二个消息的长度可选1到rest之间的任意长度，统计所有的情况，作为当前层的方案数。
每一层返回什么：返回当前层的方案数。

当数据比较大时，运行超时，如果进一步加大数据，会造成栈内存溢出（StackOverflowError）。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回可以被压缩为长度为 N 的不同消息的数量
     * @param N int 数据包的总字节数
     * @return int
     */
    //取余常数
    int mod=998244353;
    public int messageCount (int N) {
        //递归
        return dfs(N);
    }

    private int dfs(int rest){
        //递归终止条件
        if(rest==0) return 1;
        //小于5不可压缩
        if(rest<5) return 0;
        //先选定第一个数字4，然后不断地尝试第二个数字
        rest-=4;
        int res=0;
        for(int i=1;i<=rest;i++){
            res=(res+dfs(rest-i))%mod;
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：每一层都有rest种选择，所以递归的次数为 $n!$ 级别，所以时间复杂度为 $O(n!)$ 。
空间复杂度：需要额外深度为 $n!$ 级别的递归栈，所以空间复杂度为 $O(n!)$ 。

方法二（动态规划）

1.解题思路

我们可以将一组的两个消息绑在一起进行分析，问题转化为有多少种分组的方案。根据题目条件，一组至少分5个消息，至多分n个消息。所以当前长度（长度为n）消息的方案数 $f[n]=f[n-5]+f[n-4]+……+f[1]+f[0]$ ，然后再分析长度为 $n-1$ 时的方案数 $f[n-1]=f[n-4]+f[n-3]+……+f[1]+f[0]$ ，两式子相减，可得： $f[n]-f[n-1]=f[n-5]$ ，于是，可以根据这个递推关系，进行动态规划。

状态定义： $dp[i]$ 表示长度为i时，对应的消息压缩的方案数。
状态初始化：当长度小于5时，不可压缩，直接赋为0。长度刚好为5时，只有一种方案，赋为1。
状态转化：根据前面的分析， $dp[i]=dp[i-1]+dp[i-5]$ 。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回可以被压缩为长度为 N 的不同消息的数量
     * @param N int 数据包的总字节数
     * @return int
     */
    //取余常数
    int mod=998244353;
    public int messageCount (int N) {
        //不可压缩的情况
        if(N<5) return 0;
        //定义dp数组
        int[] dp=new int[N+1];
        //初始化
        dp[5]=1;
        for(int i=6;i<=N;i++){
            //状态转换
            dp[i]=(dp[i-1]+dp[i-5])%mod;
        }
        return dp[N];
    }
}

3.复杂度分析

时间复杂度：假设消息长度为n，循环体需要执行 $n-5$ 次，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外长度为 $n+1$ 的空间，所以空间复杂度为 $O(n)$ 。