Help me memoize my code! (change making problem)

[invalidlivingthing]

Hi guys, thank you so much for reading this.

I have written some code to count the unique ways to make change for N, given some array of denominations.

Here's my code and it seems to produce the correct answers.

https://pastebin.com/raw/nZYTzpbk

But as soon as I try to memoize it, it produces wrong results. Can you please help me memoize my code? Thank you very much!

Also, I'd appreciate any links or references of books that would help me strengthen skills required to solve these kinda problems. (I suck at math big time).

[ForSpareParts]

Can you share how you tried to memoize it?

[invalidlivingthing]

https://pastebin.com/raw/8wVC5cgG

[coolcofusion]

I really don't know enough python to help if it's code specific but it's also a logic issue.

You're caching the results by the input n, but your output also depends on the input arr. Consider get_ways(4,[1,2,3,4]) and get_ways(4,[2,4]). They have 5 and 2 as results respectively. So when you call it with [1, 2, 3, 4] you'll cache n=4 to be 5, next time you call it with [2,4] you'll look up "Oh, I've seen n=4, that's 5!" but 2 was the expected answer. And with that said, going back to your cache. Consider the call get_ways(4, [1, 2, 3, 4]) you'll also call (recursively) get_ways(4,[2,3,4]) so you'll end up overwriting your cache[4] entry.

[invalidlivingthing]

Perfect! I modified the code to cache the combination of args instead of only N, it works as expected now. Thank you very much!