消息压缩

[编程题]消息压缩

热度指数：985 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

长度为n的线段有多少种切割方法，切割时两个为一组，一组中第一个数字必须为4，两个数字都必须为正整数，例如n=10有两种：

| 4 | 6 |

| 4 | 1 | 4 | 1 |

注意，在所有可能的结构中，消息的长度不可以为 0。也就是说，不能出现这样的消息：| 4 | 0 |。

当然，答案可能会很大，所以你需要给出答案模 998244353 之后的结果。

示例1

输入

输出

示例2

输入

输出

说明

| 4 | 7 |，| 4 | 1 | 4 | 2 |，| 4 | 2 | 4 | 1 |，共计三种不同的消息。

备注:

数据范围：
- 对于 30% 的数据，
- 对于 60% 的数据，
- 对于 100% 的数据，

算法知识视频讲解

Python

牛客81652600号

提交结果：答案正确运行时间：398ms 占用内存：6520KB 使用语言：Python 3 用例通过率：100.00%

class Solution:
    def messageCount(self , N ):
    # write code here
    if N < 11:
        return N // 5
    d = [(i + 6) // 5 for i in range(5)]
    for i in range(11, N+1):
        d[(i-1)%5] = (d[(i-1-1)%5] + d[(i-5-1)%5]) % 998244353
    return d[(N-1)%5]

提交结果：答案正确运行时间：272ms 占用内存：43960KB 使用语言：Python 3 用例通过率：100.00%

class Solution:
    def messageCount(self , N ):
    # write code here
    d = [i // 5 for i in range(11)]
    for i in range(11, N+1):
        d.append((d[i-1] + d[i-5]) % 998244353)
    return d[N]

提交结果：运行超时运行时间：2001ms 占用内存：6520KB 使用语言：Python 3 用例通过率：60.00%

class Solution:
    def messageCount(self , N ):
        # write code here
        d = {0: 0}
        def count(rest):
            try:
                return d[rest]
            except:
                pass
            if rest - 4 < 1:
                return 0
            result = 1
            for i in range(5, rest - 4):
                result += count(i)
            result = result % 998244353
            d[rest] = result
            return result
        return count(N)

编辑于 2020-07-30 14:09:01 回复(0)