'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