Solving Dynamic Programming Problem on coins
<p>Consider a below problem</p>

<blockquote>
  <p>Given an infinite number of nickels (5 cents) and pennies (1 cent). Write a code to calculate a number of ways of representing n cents.</p>
</blockquote>

<p>My code</p>

<pre><code>def coins(n):
    if (n &lt; 0):
        return 0
    elif (n == 0):
        return 1
    else:
        if (cnt_lst[n-1] == 0):
            cnt_lst[n-1] = coins(n-1) + coins(n-5)
        return cnt_lst[n-1]

if __name__ == "__main__":
    cnt = int(input())
    cnt_lst = [0] * cnt #Memiozation
    ret = coins(cnt)
    print(ret)
</code></pre>

<p>Above approach counting repeated patterns more than one (obviously I'm not checking them explicitly).</p>

<blockquote>
  <p>[5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1], etc</p>
</blockquote>

<p>Maintaining another list which holds the previously seen patterns will require a lot of memory as <code>n</code> grows. What another approach we can use to overcome this problem?</p>