📣 独立日限时特惠: VIP通行证立减$68
查看: 1358| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

[动态规划] 上周周赛1886题超时 如何优化

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 TensorKeras 于 2021-5-19 21:02 编辑

50个case过了24个 TLE

  1. # l: number of sticks lower than current select
  2. # h: number of sticks higher than current select

  3. class Solution:
  4.     def rearrangeSticks(self, n: int, k: int) -> int:
  5.         M = 10**9+7
  6.         
  7.         @lru_cache(None)
  8.         def dp2(l, h, k):
  9.                         # if no higher sticks to finish rest of k, or more than k finished, or k finished but remaining higher sticks
  10.             if h < k or k < 0 or (k == 0 and h > 0):
  11.                 return 0
  12.                         # finish all sticks
  13.             if l + h == 0:
  14.                 return int(k == 0)
  15.             ans = 0
  16.             for i in range(h):
  17.                 ans += dp2(l + i, h - i - 1, k - 1)
  18.             for j in range(l):
  19.                 ans += dp2(l - 1, h, k)
  20.             return ans

  21.         return dp2(0, n, k) % M
复制代码



上一篇:新手小白刷题疑惑(是否买会员?已经上过61b 之后看什么公开课复习)
下一篇:leetcode microsoft list
推荐
lllxin37 2021-5-20 08:47:35 | 只看该作者
全局:
感觉不应该全部用加法。需要乘法加速

dp[i][k] = dp[i-1][k-1] + (i - 1) * dp[i-1][k]

回复

使用道具 举报

🔗
speedmancs 2021-5-20 12:05:29 | 只看该作者
全局:
这个是O(N2K)吧,我也TLE了,看了discuss才焕然大悟有O(nk)的DP, 诀窍是考虑先放置rightmost的棍子。。。
回复

使用道具 举报

🔗
maristie 2021-5-20 19:54:52 | 只看该作者
全局:
我和你一样。
一开始写的是
dp(n, k) = sum { dp(n - 1, k - 1) + dp(n - 2, k - 1) * P(n-1 1) + ... + dp(n - i, k - 1) * P(n-1 i-1) + ... + dp(k - 1, k - 1) * P(n-1 n-k) }

如果 n = 500 估计能过,但 n = 1000 就比较压线了。我试了 bottom up 和 top down memoization,后者能节约一些时间,但它的test case里大的input不少,没辙。
后来观察一下发现右边的式子乘以 n 再加上 dp(n, k - 1) 就能得到更简单的递推关系

dp(n + 1, k) = dp(n, k) * n + dp(n, k - 1)

以前记得被坑过一次类似的,忘了具体哪题了
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
 楼主| TensorKeras 2021-5-21 10:35:26 | 只看该作者
全局:
披星戴月的想你 发表于 2021-5-21 02:20
 N155611537   同学们我们加个好友吧  组个队

哈哈 还没到参加比赛地步 都是结束了以后自己再做 最高纪录也是两个小时4题
回复

使用道具 举报

🔗
 楼主| TensorKeras 2021-5-21 10:40:16 | 只看该作者
全局:
maristie 发表于 2021-5-20 11:54
我和你一样。
一开始写的是
dp(n, k) = sum { dp(n - 1, k - 1) + dp(n - 2, k - 1) * P(n-1 1) + ... +  ...

谢谢 看来还是只能用乘法了 我在想我第二个loop可不可以再优化一下
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表