知道秘密的人数
难度:
标签:
题目描述
代码结果
运行时间: 23 ms, 内存: 16.2 MB
解释
方法:
本题使用动态规划方法来解决问题。定义dp[i]为第i天新知道秘密的人数。我们维护一个前缀和数组pre，其中pre[i]为直到第i天总共知道秘密的人数。对于每一天j，我们更新dp[j]为在第j-delay天知道秘密的人数减去第j-forget天知道秘密的人数（因为在第j-forget天的人在第j天已经忘记了秘密，不能再传播）。最后，根据forget的值来决定总的知道秘密的人数，如果forget小于n，则结果为pre[n-1]减去pre[n-forget-1]；否则，结果为pre[n-1]。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在计算第j天新知道秘密的人数时，要使用第j-delay天和第j-forget天知道秘密的人数差？
▷🦆
当j小于forget时，为何可以认为从第j-delay天开始的所有人都是新知道秘密的？是否考虑了j-delay小于0的情况？
▷🦆
在计算前缀和数组pre时，为什么直接使用dp数组的初始值来初始化pre？有没有特殊的考虑？
▷🦆
如果delay或forget的值非常接近n，这会对算法的输出或性能有什么特别的影响吗？
▷