fork download
copy 
  1. # your code goes here
  2.  
  3. mod = 1e9 + 7
  4.  
  5. # @lru_cache(maxsize=None)
  6. def solve(n,k,target,dp):
  7.     if n==0 and target==0:
  8.         return 1
  9.     if n<0 or target<0:
  10.         return 0
  11.     if dp[n][target]!=-1:
  12.         return dp[n][target]
  13.  
  14.     ans = 0
  15.     for i in range(1,k+1):
  16.         ans = (ans%mod + solve(n-1,k,target-i,dp)%mod)%mod
  17.  
  18.  
  19.     dp[n][target]=int(ans)
  20.     return dp[n][target]
  21.  
  22.  
  23. class Solution:  
  24.  
  25.     def method1(self, n: int, k: int, target: int) -> int:
  26.         dp = [[-1]*(target+2)]*(n+1)
  27.         # dp = [[-1] * (target+2) for _ in range(n+1)]
  28.         return solve(n,k,target,dp)
  29.  
  30.     def method2(self, n: int, k: int, target: int) -> int:
  31.         # dp = [[-1]*(target+2)]*(n+1)
  32.         dp = [[-1] * (target+2) for _ in range(n+1)]
  33.         return solve(n,k,target,dp)
  34.  
  35. obj = Solution()
  36. print(obj.method1(2,6,7))
  37. print(obj.method2(2,6,7))
Success #stdin #stdout 0.03s 9280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
6
https://ideone.com/KDypbC
language:
Python 3 (python  3.12)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!