Smallest integer with k 1-bits that is the sum of two integers with g,h 1-bits respectively
We are looking for a sum $z = x + y$, where $z$ has $k$ bits set, $x$ and $y$ have $g$ and $h$ bits set, and $z$ is as small as possible. We assume $g ≥ h$. A solution can be found directly, without any dynamic programming.

We add the numbers $x$ and $y$ from the lowest to the highest bit, taking carries into account. If we add two bits 0 + 0 without a carry, these bits can be removed without changing the number of bits set, but making the result smaller. 

We can also take any pairs where we add 1 + 0 without carry, or 0 + 1 without carry, and move those pairs to the lowest bit positions. This doesn't change the number of bits set, but moving a 1 bit in the result to a lower bit position will not make the result larger, but may make it smaller. 

Now if we add two bits 0 + 0 with carry, then we can remove these bits as well, but it is slightly more complicated. Obviously we can remove them if they are the highest bits. Otherwise, since adding 0 + 0 with or without carry does not produce a carry, and we removed all pairs 0 + 0 without carry, and moved all pairs 0 + 1 or 1 + 0 without carry to the lowest bit positions, the next higher bits must be 1 + 1. Adding 0 + 0 with carry gives a result of 1 and no carry, then adding 1 + 1 without carry gives a result of 0 with a carry. If we remove the two 0 bits, then we add 1 + 1 with carry, which gives a result of 1 with a carry. The number of bits set is unchanged, but a zero bit is removed in the result, making the result smaller. 

So we are adding any number of pairs 0 + 1 or 1 + 0, then we may have a pair 1 + 1 producing a carry, followed by any number of pairs 1 + 1, 1 + 0 or 0 + 1. Starting with the addition 1+1 we will always have a carry, and adding 1 + 1 with carry produces a 1 with carry, while adding 1 + 0 or 0 + 1 with carry produces a 0 with carry. Reordering these pairs makes no difference to the number of bits set, but by moving all pairs 1 + 1 as far as possible to the lower positions we move 1-bits to lower positions in the result, making the result smaller. 

Adding the initial 1+0 and 0+1 pairs produces exactly one bit set in the output for each bit set in the input. Adding 1+1 produces 0 output bits; each further pair produces one output bit set less than the input bits, and finally one bit will be set in the output from the final carry. If this optional range consists of j pairs, then we lose j output bits (for example, 111 + 111 = 1110, j = 3, six bits set in the input, 3 bits set in the output).

We see that we have no solution if $k &gt; g + h$. If $k = g + h$ then one optimal solution is $x = (2^g - 1)·2^h$, y = (2^h - 1). 

If $k &lt; g + h$, then we let $j = (g + h) - k$. We need to lose exactly $j$ bits set, so the range of bit producing carries must be $j$ bits long. In this range, from j+1 to 2j bits are initially set; we get the smallest possible sum if we have as many pairs 1+1 as possible. If g + h ≤ j then there is no solution. We construct the numbers x, y as follows: 

We have $a$ 1+1 pairs, where $a = min (k, j, h)$. Then we add $b = j-a$ pairs at higher and $c = k - a$ pairs at lower bit positions. Of these pairs, we have $g-a$ pairs 1+0, and $h-a$ pairs 0+1.

As an example: Let k = 10, g = 14, h = 3. j = 7, a = min (k, j, h) = min (10, 7, 3) = 3, b = j-a = 7-3 = 4, c = k - a = 10 - 3 = 7. We have

x =   1111 111 1111111
y =   0000 111 0000000
z = 1 0000 110 1111111