title: Dynamic Programming: Tabulation of a Recursive Relation
body: <p>The following recursive relation solves a variation of the coin exchange problem. Count the number of ways in which we can sum to a required value, while keeping the number of summands even:</p>
  
  <pre><code>def count_even(coins, num_coins, req_sum, parity):
      if req_sum &lt; 0:
          return 0
      if req_sum == 0 and not parity:
          return 1
      if req_sum == 0 and parity:
          return 0
      if num_coins == 0:
          return 0
      count_wout_high_coin = count_even(coins, num_coins - 1, req_sum, parity)
      count_with_high_coin = count_even(coins, num_coins, req_sum - coins[num_coins - 1], not parity)
      return count_wout_high_coin + count_with_high_coin
  </code></pre>
  
  <p>This code would yield the required solution if called with <code>parity = False</code>.</p>
  
  <p>I am having issues implementing a tabulation technique to optimize this algorithm. On a first attempt I tried to follow the same pattern as for other DP problems, and took the parity as another parameter to the problem, so I coded this triple loop:</p>
  
  <pre><code>def count_even_tabulation(S, m, n):
      if m &lt;= 0 or n &lt; 0:
          return 0
      if n == 0:
          return 1
      table = [[[0 for x in range(m)] for x in range(n + 1)] for x in range(2)]
      for j in range(m):
          table[0][0][j] = 1
          table[1][0][j] = 0
      for p in range(2):
          for i in range(1, n + 1):
              for j in range(m):
                  y = table[p][i][j - 1] if j &gt;= 1 else 0
                  x = table[1 - p][i - S[j]][j] if i - S[j] &gt;= 0 else 0
                  table[p][i][j] = x + y
      return table[0][n][m - 1]
  </code></pre>
  
  <p>However, this approach is not creating the right tables for parity equal to 0 and equal to 1:</p>
  
  <pre><code>[1, 1, 1]
  [0, 0, 0]
  [0, 0, 0]
  [0, 0, 0]
  [0, 0, 0]
  
  [0, 0, 0]
  [1, 1, 1]
  [0, 1, 1]
  [0, 0, 1]
  [0, 0, 0]
  </code></pre>
  
  <p>How can I adequately implement a tabulation approach for the given recursion relation?</p>