Stone Game Solutions in C++

/// Source : https://leetcode.com/problems/stone-game/description/
/// Author : liuyubobobo
/// Time   : 2018-07-28

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    bool stoneGame(vector<int>& piles) {

        int n = piles.size();
        vector<vector<vector<int>>> dp(2, vector<vector<int>>(n, vector<int>(n, INT_MIN)));

        return play(0, piles, 0, n-1, dp) > 0;
    }

private:
    int play(int player, const vector<int>& piles, int l, int r,
                vector<vector<vector<int>>>& dp){

        if(l == r){
            if(player == 0)
                return dp[player][l][r] = piles[l];
            else
                return dp[player][l][r] = -piles[l];
        }

        if(dp[player][l][r] != INT_MIN)
            return dp[player][l][r];

        int res = 0;
        if(player == 0)
            res = max(piles[l] + play(1 - player, piles, l + 1, r, dp),
                      piles[r] + play(1 - player, piles, l, r - 1, dp));
        else
            res = max(-piles[l] + play(1 - player, piles, l + 1, r, dp),
                      -piles[r] + play(1 - player, piles, l, r - 1, dp));
        return dp[player][l][r] = res;
    }
};


void print_bool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    vector<int> piles1 = {5, 3, 4, 5};
    print_bool(Solution().stoneGame(piles1));

    return 0;
}

/// Source : https://leetcode.com/problems/stone-game/description/
/// Author : liuyubobobo
/// Time   : 2018-08-02

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    bool stoneGame(vector<int>& piles) {

        int n = piles.size();
        vector<vector<vector<int>>> dp(2, vector<vector<int>>(n, vector<int>(n, -1)));

        for(int i = 0 ; i < n ; i ++){
            dp[0][i][i] = piles[i];
            dp[1][i][i] = -piles[i];
        }

        for(int sz = 2 ; sz <= n ; sz ++)
            for(int i = 0; i + sz - 1 < n ; i ++){
                dp[0][i][i + sz - 1] = max(piles[i] + dp[1][i + 1][i + sz - 1],
                                           piles[i + sz - 1] + dp[1][i][i + sz - 2]);
                dp[1][i][i + sz - 1] = max(-piles[i] + dp[0][i + 1][i + sz - 1],
                                           -piles[i + sz - 1] + dp[0][i][i + sz - 2]);
            }

        return dp[0][0][n - 1];
    }
};


void print_bool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    vector<int> piles1 = {5, 3, 4, 5};
    print_bool(Solution().stoneGame(piles1));

    return 0;
}

/// Source : https://leetcode.com/problems/stone-game/description/
/// Author : liuyubobobo
/// Time   : 2018-08-03

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Just use 2d dp array and consider two moves by each player together:)
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    bool stoneGame(vector<int>& piles) {

        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MIN));

        return play(piles, 0, n-1, dp) > 0;
    }

private:
    int play(const vector<int>& piles, int l, int r, vector<vector<int>>& dp){

        if(l + 1 == r)
            return abs(piles[l] - piles[r]);

        if(dp[l][r] != INT_MIN)
            return dp[l][r];

        return dp[l][r] = max(
                abs(piles[l] - piles[l + 1]) + play(piles, l + 2, r, dp),
                abs(piles[l] - piles[r]) + play(piles, l + 1, r - 1, dp));
    }
};


void print_bool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    vector<int> piles1 = {5, 3, 4, 5};
    print_bool(Solution().stoneGame(piles1));

    return 0;
}

/// Source : https://leetcode.com/problems/stone-game/description/
/// Author : liuyubobobo
/// Time   : 2018-08-03

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Just use 2d dp array and consider two moves by each player together:)
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    bool stoneGame(vector<int>& piles) {

        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MIN));

        for(int i = 0; i + 1 < n; i ++ )
            dp[i][i + 1] = abs(piles[i] - piles[i + 1]);

        for(int sz = 4; sz <= n; sz ++)
            for(int i = 0; i + sz - 1 < n; i ++)
                dp[i][i + sz - 1] = max(
                        abs(piles[i] - piles[i + 1]) + dp[i + 2][i + 3],
                        abs(piles[i] - piles[i + sz - 1]) + dp[i + 1][i + sz - 2]);
        return dp[0][n - 1];
    }
};


void print_bool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    vector<int> piles1 = {5, 3, 4, 5};
    print_bool(Solution().stoneGame(piles1));

    return 0;
}

/// Source : https://leetcode.com/problems/stone-game/description/
/// Author : liuyubobobo
/// Time   : 2018-08-03

#include <iostream>
#include <vector>

using namespace std;


/// Mathematic, the answer will always be true!
/// Since the player can technically take all the stones from even-index piles,
/// or take all the stones from odd-index piles
/// One of the two strategy must win:)
///
/// Time Complexity: O(1)
/// Space Complexity: O(1)
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};


void print_bool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    vector<int> piles1 = {5, 3, 4, 5};
    print_bool(Solution().stoneGame(piles1));

    return 0;
}