Stone Game III Solutions in C++

/// Source : https://leetcode.com/problems/stone-game-iii/
/// Author : liuyubobobo
/// Time   : 2020-04-04

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {

        int n = stoneValue.size();

        vector<int> postsum(n + 1, 0);
        for(int i = n - 1; i >= 0; i --) postsum[i] = postsum[i + 1] + stoneValue[i];

        vector<vector<int>> dp(2, vector<int>(stoneValue.size(), INT_MIN));
        int x = dfs(stoneValue, 0, 0, dp, postsum);
//        cout << x << endl;
        if(x > postsum[0] - x) return "Alice";
        else if(x < postsum[0] - x) return "Bob";
        return "Tie";
    }

private:
    int dfs(const vector<int>& values, int index, int player,
            vector<vector<int>>& dp, const vector<int>& postsum){

        if(index >= values.size()) return 0;
        if(dp[player][index] != INT_MIN) return dp[player][index];

        int sum = 0, res = INT_MIN;
        for(int i = 0; i < 3 && index + i < values.size(); i ++){
            sum += values[index + i];
            int tres = sum + postsum[index + i + 1] - dfs(values, index + i + 1, 1 - player, dp, postsum);
//            cout << "playe = " << player << " ; index = " << index << " : " << tres << endl;
            res = max(res, tres);
        }
        return dp[player][index] = res;
    }
};


int main() {

    vector<int> values1 = {1, 2, 3, 7};
    cout << Solution().stoneGameIII(values1) << endl;
    // Bob

    vector<int> values2 = {1, 2, 3, -9};
    cout << Solution().stoneGameIII(values2) << endl;
    // Alice

    vector<int> values3 = {1, 2, 3, 6};
    cout << Solution().stoneGameIII(values3) << endl;
    // Tie

    vector<int> values4 = {1,2,3,-1,-2,-3,7};
    cout << Solution().stoneGameIII(values4) << endl;
    // Alice

    vector<int> values5 = {-1, -2, -3};
    cout << Solution().stoneGameIII(values5) << endl;
    // Tie

    return 0;
}

/// Source : https://leetcode.com/problems/stone-game-iii/
/// Author : liuyubobobo
/// Time   : 2020-04-08

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// DP
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {

        int n = stoneValue.size();

        vector<int> postsum(n + 1, 0);
        for(int i = n - 1; i >= 0; i --) postsum[i] = postsum[i + 1] + stoneValue[i];

        vector<vector<int>> dp(2, vector<int>(n + 1, INT_MIN));
        dp[0][n] = dp[1][n] = 0;
        dp[0][n - 1] = dp[1][n - 1] = stoneValue[n - 1];

        for(int start = n - 2; start >= 0; start --)
            for(int player = 0; player <= 1; player ++){
                int sum = 0;
                for(int i = 0; i < 3 && start + i < n; i ++){
                    sum += stoneValue[start + i];
                    dp[player][start] = max(dp[player][start],
                                            sum + postsum[start + i + 1] - dp[1 - player][start + i + 1]);
                }
            }

        if(dp[0][0] > postsum[0] - dp[0][0]) return "Alice";
        else if(dp[0][0] < postsum[0] - dp[0][0]) return "Bob";
        return "Tie";
    }
};


int main() {

    vector<int> values1 = {1, 2, 3, 7};
    cout << Solution().stoneGameIII(values1) << endl;
    // Bob

    vector<int> values2 = {1, 2, 3, -9};
    cout << Solution().stoneGameIII(values2) << endl;
    // Alice

    vector<int> values3 = {1, 2, 3, 6};
    cout << Solution().stoneGameIII(values3) << endl;
    // Tie

    vector<int> values4 = {1,2,3,-1,-2,-3,7};
    cout << Solution().stoneGameIII(values4) << endl;
    // Alice

    vector<int> values5 = {-1, -2, -3};
    cout << Solution().stoneGameIII(values5) << endl;
    // Tie

    return 0;
}

/// Source : https://leetcode.com/problems/stone-game-iii/
/// Author : liuyubobobo
/// Time   : 2020-04-08

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// One dimensional DP without postsum
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {

        int n = stoneValue.size();
        vector<int> dp(n + 1, INT_MIN);
        dp[n] = 0;
        dp[n - 1] = stoneValue[n - 1];

        for(int start = n - 2; start >= 0; start --){
            int sum = 0;
            for(int i = 0; i < 3 && start + i < n; i ++){
                sum += stoneValue[start + i];
                dp[start] = max(dp[start], sum - dp[start + i + 1]);
            }
        }

        if(dp[0] > 0) return "Alice";
        else if(dp[0] < 0) return "Bob";
        return "Tie";
    }
};


int main() {

    vector<int> values1 = {1, 2, 3, 7};
    cout << Solution().stoneGameIII(values1) << endl;
    // Bob

    vector<int> values2 = {1, 2, 3, -9};
    cout << Solution().stoneGameIII(values2) << endl;
    // Alice

    vector<int> values3 = {1, 2, 3, 6};
    cout << Solution().stoneGameIII(values3) << endl;
    // Tie

    vector<int> values4 = {1,2,3,-1,-2,-3,7};
    cout << Solution().stoneGameIII(values4) << endl;
    // Alice

    vector<int> values5 = {-1, -2, -3};
    cout << Solution().stoneGameIII(values5) << endl;
    // Tie

    return 0;
}

/// Source : https://leetcode.com/problems/stone-game-iii/
/// Author : liuyubobobo
/// Time   : 2020-04-08

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// One dimensional DP without postsum
/// Space Optimized
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {

        int n = stoneValue.size();
        vector<int> dp(4, 0);
        for(int start = n - 1; start >= 0; start --){
            int sum = 0;
            dp[start % 4] = INT_MIN;
            for(int i = 0; i < 3 && start + i < n; i ++){
                sum += stoneValue[start + i];
                dp[start % 4] = max(dp[start % 4], sum - (start + i + 1 < n ? dp[(start + i + 1) % 4] : 0));
            }
        }

        if(dp[0] > 0) return "Alice";
        else if(dp[0] < 0) return "Bob";
        return "Tie";
    }
};


int main() {

    vector<int> values1 = {1, 2, 3, 7};
    cout << Solution().stoneGameIII(values1) << endl;
    // Bob

    vector<int> values2 = {1, 2, 3, -9};
    cout << Solution().stoneGameIII(values2) << endl;
    // Alice

    vector<int> values3 = {1, 2, 3, 6};
    cout << Solution().stoneGameIII(values3) << endl;
    // Tie

    vector<int> values4 = {1,2,3,-1,-2,-3,7};
    cout << Solution().stoneGameIII(values4) << endl;
    // Alice

    vector<int> values5 = {-1, -2, -3};
    cout << Solution().stoneGameIII(values5) << endl;
    // Tie

    return 0;
}