Q$3.(15$ pts$)$ Given a positive integer, $,$ find the number of different ways to write $$ as the

sum of $1,3$ and $4.$ For example, if $=5,$ the answer is $6$ because:

$5=1+1+1+1+1$

$=1+1+3$

$=1+3+1$

$=3+1+1$

$=1+4$

$=4+1$

Note that $1+4$ and $4+1$ are two different ways to perform the sum.

Design a dynamic programming algorithm, which finishes in O$($n$)$ to return the result. You

may describe your algorithm by stating the recurrence relation and the base case.