I have found two ways of applying dynamic programming to the coin change problem of finding the minimum number of coins from a given set of denominations to make a given sum. I wanted to know if one is better than the other:
def money_dyn1(m, coins): a = [[float("+inf") for j in range(m + 1)] for i in range(len(coins) + 1)] for i in range(len(a)): a[i] = 0 for i in range(1, len(a)): for j in range(1, len(a)): if coins[i - 1] > j: # if the coin is bigger than the sum to reach a[i][j] = a[i - 1][j] else: a[i][j] = min(a[i - 1][j], a[i][j - coins[i - 1]] + 1) print(a[-1][m])
def money_dyn2(m, coins): a = [None for j in range(m + 1)] a = 0 for i in range(0, len(a)): for c in coins: if i + c < len(a) and a[i] != None: if a[i + c] == None or a[i + c] > a[i]: a[i + c] = a[i] + 1 return a[m]
I find the later much simpler to understand, but when I lookup examples on the internet about DP applied to this problem, it seems that most of the solutions implement the first implementation (using the 2D array).
Is one of those implementation better than the other ? What are the differences between those ? (both mathematically and algorithmically)