# Game theory — Stone games

## Stone Game

Aug 5, 2021

--

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.