Python에서 목표에 도달하기 위한 코인 조합의 수를 찾는 프로그램

<시간/>

코인 목록과 다른 가치 금액이 있다고 가정하면 해당 합계 금액에 해당하는 조합의 수를 찾아야 합니다. 답이 매우 크면 결과를 10^9 + 7로 수정합니다.

따라서 입력이 동전 =[2, 5] amount =10과 같으면 출력은 2가 됩니다. 이러한 조합을 만들 수 있으므로 - [2, 2, 2, 2, 2], [5, 5]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=10^9 + 7
dp :=amount + 1과 같은 크기의 리스트, 0으로 채움
dp[0] :=1
동전의 각 d에 대해 다음을 수행합니다.
- 범위 1에서 dp 크기까지의 i에 대해 다음을 수행합니다.
  - i - d>=0이면
    - dp[i] :=dp[i] + dp[i - d]
return(dp의 마지막 요소) mod m

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution:
   def solve(self, coins, amount):
      dp = [0] * (amount + 1)
      dp[0] = 1
      for d in coins:
         for i in range(1, len(dp)):
            if i - d >= 0:
               dp[i] += dp[i - d]
      return dp[-1] % (10 ** 9 + 7)
ob = Solution()
coins = [2, 5]
amount = 10
print(ob.solve(coins, amount))

입력

[2, 5], 10