【題解】LeetCode 877. Stone Game

【題目敘述】https://leetcode.com/problems/stone-game/
【解題想法】參考類似題 TIOJ 1029 . A遊戲 【題解

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n, s = 0, a[505][505];
        n = piles.size();
        for (int i = 2; i < n+2; i++){
            a[i][i] = piles[i-2];
            s += a[i][i];
            for (int j = i-1; j >= 2; j--){
                a[j][i] = max(a[j][j] + min(a[j+1][i-1], a[j+2][i]),
                              a[i][i] + min(a[j][i-2], a[j+1][i-1]));
            }
        }
        if (a[2][n+1] > s - a[2][n+1]) return true;
        else return false;
    }
};
分享本文 Share with friends