Dynamic programming: find possible sums of given digits to reach given sum

Question

Maybe anyone has idea how to solve this problem using dynamic programming: I have a natural number. Let’s name it n. Then, have digits: 1, 3, 4. I have to find all possible sums (with repetitives) of n using digits above. For example.

n=3. Then solution:
1+1+1=3
3=3

I know how to solve this problem using recursion or loops, but I really have no idea how to solve it with dynamic programming. And how to write relation for subproblems.

[So] might be helpful too – sai-kartik May 20 '20 at 21:43 — sai-kartik, May 20 '20 at 21:43
@Henry I'm sorry, I've corrected the mistake. – John McCart May 21 '20 at 08:56 — John McCart, May 21 '20 at 08:56

score 1 · Answer 1 · answered May 20 '20 at 21:39

1

Hint: condition on the first element in the sum.

answered May 20 '20 at 21:39

Robert Israel

448,999

Dynamic programming: find possible sums of given digits to reach given sum

1 Answers1