Game theory — Stone games

Of course for this problem, you can always return true. For most game theory problem, you can solve it by using a iterative way to check whether you can win or lose the game.

const int N = 510;
int f[N][N];
class Solution {
public:
vector<int> piles;
int dp(int i, int j){
if (i == j) return piles[i];
if (f[i][j] != -1) return f[i][j];
return f[i][j] = max(piles[i] - dp(i + 1, j), piles[j] - dp(i, j - 1));
}
bool stoneGame(vector<int>& piles) {
this -> piles = piles;
const int n = piles.size();
memset(f, -1, sizeof f);
return dp(0, n - 1) > 0;
}
};

My other stone game related questions can be found HERE.

I will put more game theory related problem in this article.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi