关注
你那个时间复杂度是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
相关推荐
07-13 10:24
广州南方学院 运营 
点赞 评论 收藏
分享
06-04 09:21
南宁师范大学 测试工程师 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 工作中哪个瞬间让你想离职 #
28458次浏览 198人参与
# 在职场上,你最讨厌什么样的同事 #
16330次浏览 163人参与
# 机械人,秋招第一次笔试的企业是哪家? #
41172次浏览 327人参与
# 选了这个offer,你有没有后悔? #
593051次浏览 4029人参与
# 小米硬件提前批进度交流 #
171138次浏览 1528人参与
# 机械求职避坑tips #
53495次浏览 381人参与
# 哪些公司校招卡第一学历 #
75038次浏览 307人参与
# 担心入职之后被发现很菜怎么办 #
139539次浏览 809人参与
# 入职以后才知道的校招谎言 #
89049次浏览 588人参与
# 职场常用语录大全 #
4139次浏览 30人参与
# Offer比较,你最看重什么? #
192191次浏览 1310人参与
# 华子oc时间线 #
1245081次浏览 6487人参与
# 哪些公司开提前批了? #
30069次浏览 277人参与
# 风评不好的公司,你会去吗? #
66029次浏览 463人参与
# 两会劳动法放大招 #
76716次浏览 692人参与
# 应届生初入职场,求建议 #
230322次浏览 2651人参与
# 实习如何「偷」产出? #
56404次浏览 1393人参与
# 不卡学历的大厂有哪些? #
32955次浏览 252人参与
# 校招阶段,学历VS技术哪个更重要? #
19671次浏览 206人参与
# 怎么防止在试用期被辞退 #
129210次浏览 927人参与