Sponsored
Sponsored
This approach involves using a two-pointer technique to process the tokens. By sorting the tokens array, we aim to utilize the smallest possible tokens first to maximize score when power allows, and then balance power by utilizing score if achievable.
Start by sorting the tokens array. Maintain two pointers: one at the start to play face-up when you have enough power, and the other at the end to play face-down when a score can be sacrificed to gain more power. Keep track of the current score and maximum score achieved. This greedy approach helps in maximizing score by trying to play as many tokens face-up as possible while being able to trade score for power when needed.
The time complexity is O(n log n) due to sorting the tokens array. The space complexity is O(1) as no additional space besides variables is used.
1def bagOfTokensScore(tokens, power):
2 tokens.sort()
3 left, right = 0, len(tokens) - 1
4 score, maxScore
Python's solution sorts the tokens list and uses two pointers to determine the next move. Depending on power and score, tokens are played either face-up or face-down to maximize score. Once possible moves are exhausted, the highest score achieved is returned.
In the dynamic programming approach, we consider decisions at each token in terms of playing face-up or face-down, and store results for subproblems to optimize the score obtained.
The dynamic programming table, dp[i][j], keeps track of the maximum score achievable with the first i tokens and with j power. For each token, either spend or gain power while adjusting the score, and calculate the best possible outcome for each state.
The time complexity is O(n * m) where n is the number of tokens and m is the initial power range explored. The space complexity is also O(n * m) due to the DP table usage.
#include <vector>
#include <algorithm>
using namespace std;
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(tokens.begin(), tokens.end());
vector<vector<int>> dp(tokens.size() + 1, vector<int>(power + 1, 0));
for (int i = 1; i <= tokens.size(); ++i) {
for (int j = 0; j <= power; ++j) {
if (j >= tokens[i - 1]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - tokens[i - 1]] + 1);
} else {
dp[i][j] = dp[i - 1][j];
}
if (j + tokens[i - 1] <= power && dp[i - 1][j + tokens[i - 1]] > 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j + tokens[i - 1]] - 1);
}
}
}
return dp[tokens.size()][power];
}
int main() {
vector<int> tokens = {100, 200, 300, 400};
int power = 200;
int result = bagOfTokensScore(tokens, power);
cout << "Maximum Score: " << result << endl;
return 0;
}This C++ solution similarly uses a DP approach with a 2D vector to memorize combinations of tokens played and power remaining. At every state, it computes the score obtained from playing face-up or face-down, updating the DP vector for optimality. The answer represents the maximum score possible for given initial power and tokens.