title: Algorithms - Dynamic programming - Subset sum of two arrays
body: <p>My homework include a dynamic programming question:</p>
  
  <blockquote>
    <p>Given two arrays of natural integers (a1,a2,...,an and b1,b2,...,bn)
    such all of them are smaller than n^2, and also given is a number B
    which is smaller than n^3.</p>
    
    <p>You need to determent if there is an array (c1,c2,...,cn) such:</p>
    
    <p><a href="https://i.stack.imgur.com/rqF3G.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rqF3G.png" alt="enter image description here"></a></p>
    
    <p>And for each 1 &lt;= i &lt;= n, ci = ai or ci = bi.</p>
    
    <p>*This algorithm must be written with dynamic programming.</p>
    
    <p>*Also, what would we need to change to acctually get the array c that gives us Sum(c) = B</p>
  </blockquote>
  
  <p>Another way of looking at the question is by saying that c is equal to a subset of a, and its complement subset from b.</p>
  
  <p>This is a recursive pseudo code I wrote to solve this question:</p>
  
  <pre><code>W(a,b,i, N)
      if i==-1
          if N==0     return true;
          else        return false;
      return W(a,b,i-1,N-a[i]) || W(a,b,i-1,N-b[i]);
  
  T(n) = 2^n
  </code></pre>
  
  <p>And here, to return the best path, just store this in a tree, and go over from the (good) end to the start</p>
  
  <p><strong>How can I write this with dynamic programming? Will this even help the run time? because the recursive solution has independent results.</strong></p>
  
  <p>*I searched google for this problem and found nothing but "the subset sum problem" which is different.</p>