Hacktoberfestmine/Coin-Change_Leetcode.py at main · pythonites/Hacktoberfestmine · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# https://leetcode.com/problems/coin-change/
# Python solution to leetcode problem - Coin Change
# Solution Approach - DP

import sys
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        # unbounded knapsack problem

        n=len(coins)

        maximum=sys.maxsize-1

        dp=[[0 for j in range(amount+1)] for i in range(n+1)]


        for i in range(n+1):
            for j in range(amount+1):

                if i==0:
                    dp[i][j]=maximum

                elif j==0:
                    dp[i][j]=0

                elif coins[i-1]<=j:

                    dp[i][j]= min (1+dp[i][j-coins[i-1]], dp[i-1][j])

                elif coins[i-1]>j:

                    dp[i][j] = dp[i-1][j]

        if dp[n][amount]==maximum:
            return -1

        return dp[n][amount]