关注
你那个时间复杂度是O(mn)吧?我的时间复杂度O(n),空间复杂度O(m),AC 75%,显示超时 int64_t totalWays(int n, int m)
{ deque<int> dp(m, 0); dp[0] = 1; int sum = 1; for (int i = 1; i < min(n, m); ++i) { for (int j = 0; j < i; ++j) { dp[i] += dp[j]%10007; } dp[i] += 1; sum += dp[i]; sum = sum % 10007; } if (n < m) return dp[n - 1]; for (int i = m; i < n; ++i) { int front = dp.front(); dp.pop_front(); dp.push_back(sum); sum += (sum - front); sum %= 10007; if (sum < 0) sum += 10007; } return dp[m-1] % 10007;
}
查看原帖
点赞 1
相关推荐
点赞 评论 收藏
分享
08-16 22:33
门头沟学院 Unity3D客户端 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 找工作中的小确幸 #
12768次浏览 112人参与
# 实习在多还是在精 #
4606次浏览 58人参与
# 爱玛科技集团求职进展汇总 #
30702次浏览 211人参与
# 你见过哪些工贼行为 #
4400次浏览 32人参与
# 秋招踩过的“雷”,希望你别再踩 #
24346次浏览 286人参与
# 你觉得什么岗位会被AI替代 #
6544次浏览 96人参与
# 实习下班不想学习,正常吗? #
4872次浏览 70人参与
# 校招谈薪一定要知道的事 #
4224次浏览 60人参与
# 面包vs爱情,怎么选? #
18379次浏览 194人参与
# 反问环节如何提问 #
107373次浏览 2029人参与
# 贝壳求职进展汇总 #
36560次浏览 205人参与
# 选完offer后,你后悔学机械吗? #
39713次浏览 243人参与
# 新凯来求职进展汇总 #
53330次浏览 133人参与
# 浪潮求职进展汇总 #
18161次浏览 137人参与
# 我的求职进度条 #
1952次浏览 28人参与
# 你秋招想去哪些公司 #
63620次浏览 1700人参与
# 招银网络求职进展汇总 #
174418次浏览 1005人参与
# 秋招结束之后的日子 #
89289次浏览 986人参与
# 机械人,签完三方你在忙什么? #
62037次浏览 235人参与
# 节后第一天上班,我的精神状态 #
15804次浏览 133人参与
# 应届生初入职场,求建议 #
263289次浏览 2800人参与