Cerinta completa

Given an amount and the denominations of coins available, determine how many ways change can be made for amount. There is a limitless supply of each coin type.

Example

There are ways to make change for : , , and .

Function Description

Complete the getWays function in the editor below.

getWays has the following parameter(s):

  • int n: the amount to make change for
  • int c[m]: the available coin denominations

Returns

  • int: the number of ways to make change

Input Format

The first line contains two space-separated integers and , where:
is the amount to change
is the number of coin types
The second line contains space-separated integers that describe the values of each coin type.

Constraints

  • Each is guaranteed to be distinct.

Hints

Solve overlapping subproblems using Dynamic Programming (DP):
You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times.
* Consider the degenerate cases:
– How many ways can you make change for cents?
– How many ways can you make change for cents if you have no coins?
* If you’re having trouble defining your solutions store, then think about it in terms of the base case .
– The answer may be larger than a -bit integer.

Sample Input 0

4 3
1 2 3

Sample Output 0

4

Explanation 0

There are four ways to make change for using coins with values given by :

Sample Input 1

10 4
2 5 3 6

Sample Output 1

5

Explanation 1

There are five ways to make change for units using coins with values given by :

Limbajul de programare folosit: python3

Cod:

'''
Problem: https://www.hackerrank.com/challenges/coin-change
Python 3

Thoughts: Recursive solution for the intuition.
Recursing through the possibilty of solution with nth coin 
and without nth coin. 
Bottom up DP to track overlapping subproblem solution.

Time Complexity:  O(N*M)
Space Complexity: O(N)
'''



N,M = list(map(int,input().strip().split(' ')))
coins = list(map(int,input().strip().split(' ')))

count = 0
def count_make_change_recursive(N, coins, M):
    if N < 0:
        return 0
    if N == 0:
        return 1
    if M <= 0:
        return 0
    return count_make_change(N-coins[M-1], coins, M) + count_make_change(N,coins,M-1)


def count_make_change_bottom_up(N, coins, M):
    counts = [0] * (N+1)
    counts[0] = 1
    for i in range(0, M):
        sum = 0
        for j in range(coins[i],N+1):
            counts[j] += counts[j-coins[i]]
    return counts[N]


print(count_make_change_bottom_up(N,coins,M))

Scor obtinut: 1.0

Submission ID: 464604539

Link challenge: https://www.hackerrank.com/challenges/coin-change/problem

The Coin Change Problem