'1d array or 2d array when solving dynamic programming problems
My question is how can you identify when to use a 1d array or 2d array for a dynamic programming problem. For instance, I stumbled upon the problem number of ways to make change
Here is an example:
inputs n = 12 and denominations = [2, 3, 7],
suppose you can pick an unlimited (infinite) amount of coins of each of the denominations you have. In how many ways can you make change for 12. The answer is 4
I got to the answer using dynamic programming and here is my code
def numberOfWaysToMakeChange(n, denoms):
if n == 0 or len(denoms) == 0:
return 1
ways = [[0 for _ in range(n + 1)] for _ in range(len(denoms))]
for row in ways:
row[0] = 1
for i in range(n + 1):
if i % denoms[0] == 0:
ways[0][i] = 1
for i in range(1, len(denoms)):
for j in range(1, n + 1):
if denoms[i] > j:
ways[i][j] = ways[i - 1][j]
else:
ways[i][j] = ways[i - 1][j] + ways[i][j - denoms[i]]
return ways[-1][-1]
result = numberOfWaysToMakeChange(12, [2, 3, 7])
print(result)
But online I found an answer that works as well that looks like the following
ways = [0 for _ in range(n + 1)]
ways[0] = 1
for denom in denoms:
for amount in range(1, n+1):
if denom <= amount:
ways[amount] += ways[amount - denom]
return ways[n]
How can you identify when you can use a 1d array for these kind of questions?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
