This is the pattern of the dynamic programming

Awesome code using dynamic programming

Oh ok, my mind was stuck on a way to use 1 and 2 to make 0.

But i get it now, thanks !

If you have to return nothing, there is one way to do that, right?
In the other case, you can't return 11, that's why you need to return 0.

I don't understand why countChange(0, [1, 2]) should be "1".

Like countChange(11, [5, 7]), if there is no way to use any coin, it's just 0 ?!

What is the change you use to make "1" out of countChange(0, [1, 2]) ? 1 ? 2 ?

Java Translation

duplicate of this issue

The C++ randomized tests are ridiculously more difficult than the Javascript ones. Here are a few randomized tests from the Javascript cases:

money=2962, coins=[342, 381, 358, 400]
money=0, coins=[14, 482, 58]
money=1504, coins=[376]
money=0, coins=[108, 358, 319, 439]

and the madness that are the randomized C++ cases:

money=45290, coins=[1, 2, 2052, 2414, 3758, 3768, 4685, 6607, 6852, 9886, 11599, 12309, 12537, 14983, 19645, 21142, 21952, 22199, 25886, 26096, 26608, 28288, 29523, 30689, 36574, 37546, 39867, 40640, 41033, 43250]
money=71905, coins=[1, 2, 1091, 3875, 8351, 10746, 11519, 14011, 22480, 22954, 23537, 26308, 30694, 35073, 40862, 41930, 42306, 47965, 50558, 54438, 57510, 57864, 61605, 63530, 67173, 67536]
money=71119, coins=[1, 2, 2473, 24198, 24931, 31298, 39847, 42517, 50857, 54231, 59625, 66036]

I ended up implementing an optimization just for these 1, 2, big_number, ..., big_number cases, which funnily enough is enough to pass them (assuming that the rest of your code is somewhat efficient). Otherwise a recursive solution simply isn't performant enough.

This prob is my second dp prob and i gotta say tht these probs really make u think! I feel stupid each time i am working on one! Combinatorics and prog give headache problems, i tell ya!

I agree. The C++ tests are too hard. Much harder than the tests for other languages.

I translated the simple C solution to Haskell, and it easily passed the Haskell tests. Looks like the C++ tests are much harder than the tests for other languages.

The C++ tests are much tougher than e.g. the C tests. I just tried it: A simple C solution that easily passes the C tests times out on the C++ tests. A bit unfair, I'd say. Either the C tests are too easy, or the C++ tests are too hard. I don't know which...

The C++ tests are much tougher than e.g. the C tests. I just tried it: A simple C solution that easily passes the C tests times out on the C++ tests. A bit unfair, I'd say. Either the C tests are too easy, or the C++ tests are too hard. I don't know which...

There is 1 way to get 0, and that is by having 0 coins.

Sorry @trashy_incel, this was the first time I opened an issue and I was running crazy and did not found out exactly what was happening. It seamed that for some reason, something was being cached from test to test, even though everything was instantiated inside the function, so the submit test set was giving different results on some tests. Most likely something on my side, but running out of options, decided to open an issue. I'll remember to post more information next time, and to come back after completion (after getting all tests to pass, I stumbled upon timeout, so had to rethink on a faster solution)