Leetcode coin change problem

Below the leetcode problem of coin change.

We need to return the lowest number of coins for the given amount.

This is an include-exclude approachable problem. There are multiple methods to solve this: brute-force, top-down memoization, bottom-up tabulation approaches.

In Python there is lru_cache decorator in functools module. This helps to quickly add memoization capabilities to the function.

When you decorate a function with @functools.lru_cache(maxsize=None), Python stores the function's return values for each unique set of arguments in a cache. If the function is later called with the same arguments, Python retrieves the result from the cache instead of recomputing the function. The maxsize parameter determines the size of the cache:

• If maxsize is set to None, the cache can grow without bound.
• If maxsize is set to a positive integer, the cache will hold the most recent maxsize entries and older entries are discarded as new ones are added.

I used this decorator. My observation is it is slower comparatively.

Top-down memoization method solution:

LRU cache solution:

Bottom-up tabulation solution: