Consider the following recursive function foo which takes as input a positive integer n:

def foo$($n$)$:

if n $==1$: return $1$

if n$\%2==0$: return n $+$ foo$($n$//2)$

return foo$(3*$n$+1)$

Can you implement the function foo from the previous question using dynamic programming and bottom$-$up iteration?

If yes, give an implementation; if no$,$ explain what difficulties do you encounter.