### James S. Plank

Wed Mar 1 20:20:59 EST 2017

I'm going to save you some time. (Maybe). Don't think about how to win the game. Instead, think about dynamic programming. You can solve this with recursion:
• The base case is when you can win the game in one move. Return the answer.
• Otherwise, for each value of i from 1 to maxAdd, call the method recursively on (next+i). If the answer is -1, then your opponent has lost, so i is your answer. If the answer is anything but -1, then you need to try another value of i.
• If you can't find a value of i that lets you win the game, then you lose. Return -1.
Go ahead and solve it in this manner. I've added a 4th example to main.cpp that sets goal to 1000, next to one and maxAdd to 8. You'll see that your recursive solution takes too long now, so you need to memoize by adding a cache.

### My Solution

My solution is in Solution.cpp:

 ```/* Topcoder SRM 183, D2, 350-pointer. CountGame James S. Plank Wed Mar 1 20:35:06 EST 2017 */ #include #include #include #include using namespace std; /* I've added a cache for dynamic programming to the class. */ class CountGame { public: int howMany(int maxAdd, int goal, int next); vector cache; }; int CountGame::howMany(int maxAdd, int goal, int next) { int i; /* The first time that this is called, I initialize the cache. My "empty" value is -2. This is because -1 is a valid answer. */ if (cache.size() == 0) cache.resize(goal+1, -2); /* Check the cache and return if I've already solved this value of next. */ if (cache[next] != -2) return cache[next]; /* Here's the base case of the recursion. If I can solve the problem in one move, then I return that move. */ if (goal - next + 1 <= maxAdd) return goal-next+1; /* Now I go through and test every value of i from 1 to maxAdd. If my opponent loses after I add i to next, then I win! */ for (i = 1; i <= maxAdd; i++) { if (howMany(maxAdd, goal, next+i) == -1) { cache[next] = i; return i; } } /* Otherwise, I lose. :( */ cache[next] = -1; return -1; } ```