title: 1d array or 2d array when solving dynamic programming problems
body: <p>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 <strong>number of ways to make change</strong></p>
  <p>Here is an example:
  inputs <code>n = 12</code> and <code>denominations = [2, 3, 7]</code>,
  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 <code>12</code>. The answer is <code>4</code></p>
  <p>I got to the answer using dynamic programming and here is my code</p>
  <pre><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] &gt; 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)
  </code></pre>
  <p>But online I found an answer that works as well that looks like the following</p>
  <pre><code>ways = [0 for _ in range(n + 1)]
  ways[0] = 1
  for denom in denoms:
    for amount in range(1, n+1):
      if denom &lt;= amount:
        ways[amount] += ways[amount - denom]
  
  return ways[n]
  </code></pre>
  <p>How can you identify when you can use a 1d array for these kind of questions?</p>