Game theory — Stone games

Stone Game

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.