题解 | #消息压缩#

题意

给定一个数字n，要求划分为x个 的数对，并且

方法一(暴力求解)

暴力枚举

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回可以被压缩为长度为 N 的不同消息的数量
     * @param N int 数据包的总字节数
     * @return int
     */
    const int mod = 998244353;
    int dfs (int rest) {
        if (rest == 0) return 1;    //搞定一个 
        if (rest < 5) {    //不可能分为(4,x) (x>0)的数对 
            return 0;
        }
        rest -= 4;
        int ret = 0;
        for (int i = 1;i <= rest;++ i) {
            ret += dfs (rest - i);
        }
        return ret;
    }
    int messageCount(int N) {
        return dfs(N);
    }
};

因为层有rest种选择。所以时间复杂度为 ,空间复杂度也为

方法二(正解)

看到这个题目，我就想起高中时期学过的下楼梯计数问题。和这道题目非常类似。
这也是动态规划题目的一个共性，就是从小的状态推导更大的状态。只是状态转移方程不同。
我们研究一下状态是如何转移的。
考虑每次增加1，我们有两种方法。
一种是黏在上一个分组的最后一个数上。因为题目只要求数对的前一个数为4，对后一个数没有任何要求。
在完成这种方案的思考后，我们应该想想，还有哪种情况没有考虑到？因为题目要求数字不能为0，那么显然黏在上一组最后一个数后，我们新增加的数始终不能单独成组，也就是不能待在大小为1的线段内。所以我们可以单独为它创建一个组
根据乘法原理，
所以结合起来，得到公式

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回可以被压缩为长度为 N 的不同消息的数量
     * @param N int 数据包的总字节数
     * @return int
     */
    const int mod = 998244353;
    int messageCount(int N) {
        int dp [1000001] = {0};
        dp [5] = 1;    //只有{4,1}一种分法 
        for (int i = 6;i <= N;++ i) {
            // 第一种，可以直接跟在上一组最后一个数字后面 也就是总共的对数没有变化
            // 第二种，自己单独组一个{4,1}，因为数字不可能为零，所以若跟在上一组最后一个数字后面，是不可能单独为一组的。 
            dp [i] = (dp [i - 1] + dp [i - 5]) % mod; 
        }
        return dp [N];
    }
};

因为保存了n个状态，所以空间复杂度为 ,而顺序递推的复杂度为