Dynamic Programming Pr0blem on coins

Consider a below problem 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. My code def coins(n): if (n < 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) Above appraoch counting repeated patterns more than one (obviously I'm not checking them explicitly). [5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1], etc Maintaining another list which holds the previously seen patterns will require a lot of memory as n grows. What another approach we can use to overcome this problem.