1406. Stone Game III

我覺得真的很難一眼看穿, 就算練了很多種可能

這我感覺比較像是腦力激盪, 知道要怎麼找就怎麼找

這題要分析的我覺得已經超出一般演算法的難度了, 感覺比較偏像競技程式

dp最難的地方就是寫出這個equation, 更難的是你還要從後面來？

題目在描述Alice跟Bob 開始拿石頭, 一次最多拿三顆, 然後從Alice開始

先說說一般人的想法, 一開始一定被約束在 Alice, Bob怎麼拿, 基本上就直接卡死了….

這題我還是覺得知道就知道了, 不知道大概也要想到死

首先, 無論是Alice跟Bob誰選, 基本上他們的機會是一樣的

怎麼說呢, 我們不需用管此時的選擇是誰, 我們都假設是Alice好了

dp[i]表示 從 i 到最後一個, 選了i可以拿到的最高分數是多少

所以想一下 假設後面還剩 n個stone

dp[i] 就會等於 n — dp[i + 1],另外他可以拿三次

所以就在dp[i] = n — dp[i+ 1], n — dp[i + 2], nn — dp[i + 3]中選出這次能拿的最大值

所以dp[0]可以拿的最大值就可以慢慢被推導出來

所以如果是Alice為第一個拿的人 就是 dp[0], Bob就會是 sum -dp[0]

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        vector<int> dp(stoneValue.size() + 3, 0);
        int sum = 0;
        for(int i = stoneValue.size() - 1; i >= 0; i--){
            sum += stoneValue[i];
            dp[i] = max({sum - dp[i + 1], sum - dp[i + 2],  sum - dp[i + 3]});
        }
        if(sum - dp[0] < dp[0]){
            return "Alice";
        }else if(sum - dp[0] > dp[0]){
            return "Bob";
        }
        return "Tie";
    }
};