题解 | NC603 #消息压缩#

题目描述

长度为n的线段有多少种切割方法，切割时两个为一组，一组中第一个数字必须为4，两个数字都必须为正整数，例如n=10有两种：
| 4 | 6 |
| 4 | 1 | 4 | 1 |
注意，在所有可能的结构中，消息的长度不可以为 0。也就是说，不能出现这样的消息：| 4 | 0 |。
当然，答案可能会很大，所以你需要给出答案模 998244353 之后的结果。
示例1
输入：10
返回值：2

题目分析

直观的解法可以模拟切割过程，遍历所有可能的切割情况，根据题意可知，切割的每个部分（一组两个数）至少为5，最大可以到线段的长度，当剩余的线段长度小于5时，不能再进行切割，只有剩余的线段长度刚好等于0，才算是一种方法；
图片说明

解题思路

方法1：模拟压缩过程，深度遍历所有可能的切割情况
dfs的遍历过程：

int res = 0;
dfs(n){
    if(n == 0){
        // 因为最初线段长度一定大于0，所以在后面切割过程中n等于0，刚好切割完成
        res++;
    }
    // 剩余的线段不足以维持一个组，返回
    if(n<5) return 0;
    for(int i=5;i<=n;i++){
        // 先分出一部分从5开始到n，遍历剩余n-i的部分
        dfs(n-i);
     }
}

直接dfs的过程，需要遍历很多重复的数字，每一层都要遍历n，但随着n的减少，每层遍历的次数也减少，时间复杂度约为 $O(n!)$ ，很容易超时，可以使用记忆化递归，将之前已经计算过的数字存储下来，减少遍历的次数。

方法2：找到状态转移方程，使用动态规划
1.定义 dp[i] 是线段长度为 i 时的切割方法数，初始化dp[0]为1；
2.根据方法1中的递归思路，可知：
①当 i 大于等于5时，dp[i] = dp[i-5] + dp[i-6] + ... dp[i-i]（dp[0]）等式①，
②当 i 大于5时， dp[i-1] = dp[i-6] + dp[i-7]...dp[0] 等式②；
将等式①减去等式②可得：dp[i] - dp[i-1] = dp[i-5]；
最后得到状态转移方程： dp[i] = dp[i-1] + dp[i-5]，只需要将i从6遍历到n，计算dp[n]的方法数。

代码实现

方法1：记忆化深度遍历所有可能的切割情况

    int mod = 998244353;
    HashMap<Integer, Integer> map;
    public int messageCount (int N) {
        map = new HashMap<>();
        return dfs(N);
    }
    public int dfs(int N){
        // 记忆化存储
        if(map.containsKey(N)){
             return map.get(N);
        }
        // 线段分割完成，直接完成
        if(N == 0) return 1;
        // 剩余线段长度小于5，不能分割
        if(N < 5){
            return 0;
        }
        // 记录长度为N的线段可以分割的方法种数
        int res = 0;
        // 从N中分出 长度为j （最少为5）的线段，剩余长度为 1 ~ N-j
        for(int j=5;j<=N;j++){
            // 继续递归 N-j 的部分
            if(!map.containsKey(N-j)){
                int add = dfs(N-j);
                map.put(N-j, add);
            }
            res = (res + map.get(N-j))%mod;
        }
        return res;
    }

时间复杂度： $O(n^2)$ ，使用记忆化后，每个数字只需要遍历一次，在外层的循环中，可以对之前遍历的数据直接返回，遍历的深度最多为 n/5 （每次都要减5），总次数 n^2/5，当数据量过大时，使用该方***报栈溢出错误；
空间复杂度： $O(n)$ ，递归的深度最多为 n/5，且需要 n 的空间来记忆化存储数据，所以空间复杂度为 $O(n)$ 。

方法2：动态规划

public int messageCount (int N) {
    if(N < 5) return 0;
    int[] dp = new int[N+1];
    int mod = 998244353;
    // 初始化
    dp[5] = 1;
    for(int i=6;i<=N;i++){
         // 状态转移方程 dp[i] = dp[i-1] + dp[i-5]
         dp[i] = (dp[i-1] + dp[i-5]) % mod;
    }
    return dp[N];
}

时间复杂度： $O(n)$ ，需要从6开始遍历到N，遍历的次数为 N-5，时间复杂度为 $O(n)$ ；
空间复杂度： $O(n)$ ，需要借助 N+1 空间的数组，空间复杂度为 $O(n)$ 。