877. Stone Game 石子游戏

题目描述 Alex 先拿，石子总数为奇数，每次只能拿前或后，两个人都做最优的选择，谁的石子数多谁赢，Alex 赢返回 true

定义二维数组 dp[i][j] 表示下标 i至j的元素区间先拿的人和后拿的人分别能够得到的最大石子数

状态方程： dp[i][j].first=max(piles[i]+dp[i+1][j].second, piles[j]+dp[i][j-1].second) dp[i][j].second=去除被选择的元素（ i 或 j ）的间隔元素后先拿人的最多石子数

bool stoneGame(vector<int>& piles) {
    int len=piles.size();
    vector<vector<pair<int, int>> > dp(piles.size(), vector<pair<int, int> >(len, make_pair(0,0)));
    for(int i=0;i<len;++i) {
        dp[i][i].first=piles[i];
    }

    for(int i=len-2;i>=0;--i) {
        for(int j=i+1;j<len;++j) {
            if (piles[i]+dp[i+1][j].second > piles[j]+dp[i][j-1].second) {
                dp[i][j].first=piles[i]+dp[i+1][j].second;
                dp[i][j].second=dp[i+1][j].first;
            } else {
                dp[i][j].first=piles[j]+dp[i][j-1].second;
                dp[i][j].second=dp[i][j-1].first;
            }
        }
    }

    return dp[0][len-1].first > dp[0][len-1].second;
}

状态压缩后的版本

bool stoneGame(vector<int>& piles) {
    int len=piles.size();
    vector<pair<int, int> > dp(piles.size(), make_pair(0,0));
    for(int i=0;i<len;++i)
        dp[i].first=piles[i];

    for(int i=len-2;i>=0;--i) {
        for(int j=i+1;j<len;++j) {
            int c1=piles[i]+dp[j].second;
            int c2=piles[j]+dp[j-1].second;
            if (c1 > c2) {
                dp[j].second=dp[j].first;
                dp[j].first=c1;
            } else {
                dp[j].second=dp[j-1].first;
                dp[j].first=c2;
            }
        }
    }

    return dp[len-1].first > dp[len-1].second;
}

#DP

859. Buddy Strings 89. Gray Code 格雷码