上周周赛1886题超时 如何优化

50个case过了24个 TLE

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

复制代码

感觉不应该全部用加法。需要乘法加速

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

这个是O(N2K)吧，我也TLE了，看了discuss才焕然大悟有O(nk)的DP, 诀窍是考虑先放置rightmost的棍子。。。

我和你一样。
一开始写的是
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)

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

披星戴月的想你 发表于 2021-5-21 02:20
 N155611537   同学们我们加个好友吧  组个队

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

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可不可以再优化一下