有办法让这段Python代码运行得更快吗？

huangapple
go评论123阅读模式
英文:

Anyway to make this code goes faster in python?

问题

以下是您提供的代码的翻译部分：

  1. from sys import setrecursionlimit
  2. setrecursionlimit(10 ** 6)
  4. MOD = 1000000007
  5. dp = [0] * 1000001
  7. def DP(dp, left):
  8.     if(dp[left] != 0):
  9.         return dp[left]
  10.     for i in range(1, 7):
  11.         if(left - i >= 0):
  12.             dp[left] += DP(dp, left - i)
  13.             dp[left] %= MOD
  14.     return dp[left]
  16. n = int(input())
  17. dp[0] = 1
  18. print(DP(dp, n))

请注意，这段代码的翻译并没有进行性能优化。如果您希望提高代码的运行速度，可以考虑使用迭代而不是递归来实现动态规划，这通常会更快。此外，您还可以尝试使用其他算法来解决问题，以提高性能。

英文: 
  1. from sys import setrecursionlimit
  2. setrecursionlimit(10 ** 6)
  4. MOD = 1000000007
  5. dp = [0] * 1000001
  7. def DP(dp, left):
  8.     if(dp[left] != 0):
  9.         return dp[left]
  10.     for i in range(1, 7):
  11.         if(left - i >= 0):
  12.             dp[left] += DP(dp, left - i)
  13.             dp[left] %= MOD
  14.     return dp[left]
  16. n = int(input())
  17. dp[0] = 1
  18. print(DP(dp, n))

Is there anyway to make this code goes faster? It can run when n is around 100000 but it was slowdown when n=654321. The task is to count the way to combining 1, 2, 3, 4, 5, 6 (a dice's faces) to make n. Example: when n=3, all the way to create n is 4: 1+1+1; 2+1; 1+2; 3. I was trying to use Dynamic Programming skill to solve but timeout. Thanks for your help!

答案1

得分: 0

让我们尝试使用自底向上的表格法，我们迭代地首先计算较小问题的值，然后使用这些值来计算该值。

  1. def DP(n):
  2.     MOD = 1000000007
  3.     dp = [0] * (n + 1)
  4.     dp[0] = 1
  6.     for i in range(1, n+1):
  7.         for j in range(1, 7):
  8.             if i >= j:
  9.                 dp[i] += dp[i - j]
  10.                 dp[i] %= MOD
  11.     return dp[n]
  13. n = int(input())
  14. print(DP(n))
英文:

Lets try to use a bottom-up, tabulation method, we iteratively compute the values for smaller problems first and then use these values to compute the value.

  1. def DP(n):
  2.     MOD = 1000000007
  3.     dp = [0] * (n + 1)
  4.     dp[0] = 1
  6.     for i in range(1, n+1):
  7.         for j in range(1, 7):
  8.             if i >= j:
  9.                 dp[i] += dp[i - j]
  10.                 dp[i] %= MOD
  11.     return dp[n]
  13. n = int(input())
  14. print(DP(n))

答案2

得分: 0

内部循环可以通过使用前缀和进行优化。使用长度为 n+1 的数字列表来存储前缀和。

  1. def DP(n):
  2.     MOD = 1000000007
  3.     dp = [0] * (n + 1)
  4.     dp[0] = 1
  5.     for i in range(1, n+1):
  6.         for j in range(1, min(i, 6) + 1):
  7.             dp[i] = (dp[i] + dp[i-j]) % MOD
  8.     return dp[n]
  10. n = int(input())
  11. print(DP(n))
英文:

The inner loop can be optimized by using a prefix sums. A list of numbers with list length of n+1 to store the prefix sums.

  1. def DP(n):
  2.     MOD = 1000000007
  3.     dp = [0] * (n + 1)
  4.     dp[0] = 1
  5.     for i in range(1, n+1):
  6.         for j in range(1, min(i, 6) + 1):
  7.             dp[i] = (dp[i] + dp[i-j]) % MOD
  8.     return dp[n]
  10. int(input())
  11. print(DP(n))

huangapple
  • 本文由 发表于 2023年6月12日 11:27:07
  • 转载请务必保留本文链接：https://go.coder-hub.com/76453485.html
  • combinations
  • dice
  • dynamic-programming
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定