1140. Stone Game II
Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, return максимальное количество камней, которые может получить Алиса.
Ví dụ:
Input: piles = [2,7,9,4,4]
Output: 10
Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again.
Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left.
In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.
C# lời giải
đã khớp/gốcpublic class Solution {
public int StoneGameII(int[] piles) {
int[][][] dp = new int[2][][];
for (int i = 0; i < 2; i++) {
dp[i] = new int[piles.Length + 1][];
for (int j = 0; j <= piles.Length; j++) {
dp[i][j] = new int[piles.Length + 1];
for (int k = 0; k <= piles.Length; k++) {
dp[i][j][k] = -1;
}
}
}
int f(int p, int i, int m) {
if (i == piles.Length) return 0;
if (dp[p][i][m] != -1) return dp[p][i][m];
int res = p == 1 ? 1000000 : -1;
int s = 0;
for (int x = 1; x <= Math.Min(2 * m, piles.Length - i); x++) {
s += piles[i + x - 1];
if (p == 0) {
res = Math.Max(res, s + f(1, i + x, Math.Max(m, x)));
} else {
res = Math.Min(res, f(0, i + x, Math.Max(m, x)));
}
}
return dp[p][i][m] = res;
}
return f(0, 0, 1);
}
}C++ lời giải
bản nháp tự động, xem lại trước khi gửi#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int StoneGameII(vector<int>& piles) {
int[][][] dp = new int[2][][];
for (int i = 0; i < 2; i++) {
dp[i] = new int[piles.size() + 1][];
for (int j = 0; j <= piles.size(); j++) {
dp[i][j] = new int[piles.size() + 1];
for (int k = 0; k <= piles.size(); k++) {
dp[i][j][k] = -1;
}
}
}
int f(int p, int i, int m) {
if (i == piles.size()) return 0;
if (dp[p][i][m] != -1) return dp[p][i][m];
int res = p == 1 ? 1000000 : -1;
int s = 0;
for (int x = 1; x <= min(2 * m, piles.size() - i); x++) {
s += piles[i + x - 1];
if (p == 0) {
res = max(res, s + f(1, i + x, max(m, x)));
} else {
res = min(res, f(0, i + x, max(m, x)));
}
}
return dp[p][i][m] = res;
}
return f(0, 0, 1);
}
}Java lời giải
đã khớp/gốcclass Solution {
private int f(int[] piles, int[][][] dp, int p, int i, int m) {
if (i == piles.length) {
return 0;
}
if (dp[p][i][m] != -1) {
return dp[p][i][m];
}
int res = p == 1 ? 1000000 : -1, s = 0;
for (int x = 1; x <= Math.min(2 * m, piles.length - i); x++) {
s += piles[i + x - 1];
if (p == 0) {
res = Math.max(res, s + f(piles, dp, 1, i + x, Math.max(m, x)));
}
else {
res = Math.min(res, f(piles, dp, 0, i + x, Math.max(m, x)));
}
}
return dp[p][i][m] = res;
}
public int stoneGameII(int[] piles) {
int[][][] dp = new int[2][piles.length + 1][piles.length + 1];
for (int p = 0; p < 2; p++) {
for (int i = 0; i <= piles.length; i++) {
for (int m = 0; m <= piles.length; m++) {
dp[p][i][m] = -1;
}
}
}
return f(piles, dp, 0, 0, 1);
}
}JavaScript lời giải
đã khớp/gốcvar stoneGameII = function(piles) {
const dp = Array.from({ length: 2 }, () =>
Array.from({ length: piles.length + 1 }, () =>
Array(piles.length + 1).fill(-1)
)
);
const f = (p, i, m) => {
if (i === piles.length) return 0;
if (dp[p][i][m] !== -1) return dp[p][i][m];
let res = p === 1 ? 1000000 : -1, s = 0;
for (let x = 1; x <= Math.min(2 * m, piles.length - i); x++) {
s += piles[i + x - 1];
if (p === 0) {
res = Math.max(res, s + f(1, i + x, Math.max(m, x)));
} else {
res = Math.min(res, f(0, i + x, Math.max(m, x)));
}
}
dp[p][i][m] = res;
return res;
};
return f(0, 0, 1);
};Python lời giải
đã khớp/gốcclass Solution:
def stoneGameII(self, piles: List[int]) -> int:
def f(p, i, m):
if i == len(piles):
return 0
if dp[p][i][m] != -1:
return dp[p][i][m]
res = 1000000 if p == 1 else -1
s = 0
for x in range(1, min(2 * m, len(piles) - i) + 1):
s += piles[i + x - 1]
if p == 0:
res = max(res, s + f(1, i + x, max(m, x)))
else:
res = min(res, f(0, i + x, max(m, x)))
dp[p][i][m] = res
return res
dp = [[[-1] * (len(piles) + 1) for _ in range(len(piles) + 1)] for _ in range(2)]
return f(0, 0, 1)Go lời giải
đã khớp/gốcfunc stoneGameII(piles []int) int {
dp := make([][][]int, 2)
for i := range dp {
dp[i] = make([][]int, len(piles) + 1)
for j := range dp[i] {
dp[i][j] = make([]int, len(piles) + 1)
for k := range dp[i][j] {
dp[i][j][k] = -1
}
}
}
var f func(p, i, m int) int
f = func(p, i, m int) int {
if i == len(piles) {
return 0
}
if dp[p][i][m] != -1 {
return dp[p][i][m]
}
res := 1000000
if p == 0 {
res = -1
}
s := 0
for x := 1; x <= min(2 * m, len(piles) - i); x++ {
s += piles[i + x - 1]
if p == 0 {
res = max(res, s + f(1, i + x, max(m, x)))
} else {
res = min(res, f(0, i + x, max(m, x)))
}
}
dp[p][i][m] = res
return res
}
return f(0, 0, 1)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}Algorithm
Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине mảngа кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.
Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния.
Если ход Боба, инициализировать res большим numberм, так как Боб хочет минимизировать результат.
Если ход Алисы, инициализировать res маленьким numberм, так как Алиса хочет максимизировать результат.
Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.