Skip to content

Commit b466c71

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problem: No.1563 (doocs#3884)
No.1563.Stone Game V
1 parent 826ddef commit b466c71

File tree

7 files changed

+344
-185
lines changed

7 files changed

+344
-185
lines changed

‎solution/1500-1599/1563.Stone Game V/README.md

Lines changed: 114 additions & 65 deletions
Original file line numberDiff line numberDiff line change
@@ -69,48 +69,53 @@ tags:
6969

7070
### 方法一：记忆化搜索 + 剪枝
7171

72-
我们先预处理出前缀和数组 $s$，其中 $s[i]$ 表示数组 $stoneValue$ 前 $i$ 个元素的和。
72+
我们先预处理出前缀和数组 $\textit{s}$，其中 $\textit{s}[i]$ 表示数组 $\textit{stoneValue}$ 前 $i$ 个元素的和。
7373

74-
接下来，我们设计一个函数 $dfs(i, j)$，表示数组 $stoneValue$ 中下标范围 $[i, j]$ 内的石子，Alice 能够获得的最大分数。那么答案就是 $dfs(0, n - 1)$。
74+
接下来，我们设计一个函数 $\textit{dfs}(i, j)$，表示数组 $\textit{stoneValue}$ 中下标范围 $[i, j]$ 内的石子，Alice 能够获得的最大分数。那么答案就是 $\textit{dfs}(0, n - 1)$。
7575

76-
函数 $dfs(i, j)$ 的计算过程如下：
76+
函数 $\textit{dfs}(i, j)$ 的计算过程如下：
7777

78-
- 如果 $i = j$，说明只剩下一块石子，Alice 无法进行分割，因此返回 $0$。
79-
- 否则，我们枚举分割点 $k$，即 $i \leq k \lt j$，将数组 $stoneValue$ 中下标范围 $[i, j]$ 内的石子分割为 $[i, k]$ 和 $[k + 1, j]$ 两部分，计算出 $a$ 和 $b$，分别表示两部分的石子总和。然后我们分别计算 $dfs(i, k)$ 和 $dfs(k + 1, j)$，并更新答案。
78+
- 如果 $i \geq j$，说明只剩下一块石子，Alice 无法进行分割，因此返回 $0$。
79+
- 否则，我们枚举分割点 $k$，即 $i \leq k < j$，将数组 $\textit{stoneValue}$ 中下标范围 $[i, j]$ 内的石子分割为 $[i, k]$ 和 $[k + 1, j]$ 两部分，计算出 $a$ 和 $b$，分别表示两部分的石子总和。然后我们分别计算 $\textit{dfs}(i, k)$ 和 $\textit{dfs}(k + 1, j)$，并更新答案。
8080

81-
注意，如果满足 $a \lt b$ 并且 $ans \geq a \times 2$，那么这一次枚举可以跳过；如果满足 $a \gt b$ 并且 $ans \geq b \times 2$，那么后续的枚举都可以跳过，直接退出循环。
81+
注意，如果满足 $a < b$ 并且 $\textit{ans} \geq a \times 2$，那么这一次枚举可以跳过；如果满足 $a > b$ 并且 $\textit{ans} \geq b \times 2$，那么后续的枚举都可以跳过，直接退出循环。
8282

8383
最后，我们返回答案即可。
8484

8585
为了避免重复计算，我们可以使用记忆化搜索，同时使用剪枝优化枚举的效率。
8686

87-
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为数组 $stoneValue$ 的长度。
87+
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为数组 $\textit{stoneValue}$ 的长度。
8888

8989
<!-- tabs:start -->
9090

9191
#### Python3
9292

9393
```python
94+
def max(a: int, b: int) -> int:
95+
return a if a > b else b
96+
97+
9498
class Solution:
9599
def stoneGameV(self, stoneValue: List[int]) -> int:
96100
@cache
97-
def dfs(i, j):
98-
if i == j:
101+
def dfs(i: int, j: int) -> int:
102+
if i >= j:
99103
return 0
100-
ans = a = 0
104+
ans = l = 0
105+
r = s[j + 1] - s[i]
101106
for k in range(i, j):
102-
a += stoneValue[k]
103-
b = s[j + 1] - s[i] - a
104-
if a < b:
105-
if ans >= a * 2:
107+
l += stoneValue[k]
108+
r -= stoneValue[k]
109+
if l < r:
110+
if ans >= l * 2:
106111
continue
107-
ans = max(ans, a + dfs(i, k))
108-
elif a > b:
109-
if ans >= b * 2:
112+
ans = max(ans, l + dfs(i, k))
113+
elif l > r:
114+
if ans >= r * 2:
110115
break
111-
ans = max(ans, b + dfs(k + 1, j))
116+
ans = max(ans, r + dfs(k + 1, j))
112117
else:
113-
ans = max(ans, a + dfs(i, k), b + dfs(k + 1, j))
118+
ans = max(ans, max(l + dfs(i, k), r + dfs(k + 1, j)))
114119
return ans
115120

116121
s = list(accumulate(stoneValue, initial=0))
@@ -123,44 +128,43 @@ class Solution:
123128
class Solution {
124129
private int n;
125130
private int[] s;
126-
private int[] stoneValue;
131+
private int[] nums;
127132
private Integer[][] f;
128133

129134
public int stoneGameV(int[] stoneValue) {
130135
n = stoneValue.length;
131-
this.stoneValue = stoneValue;
132136
s = new int[n + 1];
137+
nums = stoneValue;
138+
f = new Integer[n][n];
133139
for (int i = 1; i <= n; ++i) {
134-
s[i] = s[i - 1] + stoneValue[i - 1];
140+
s[i] = s[i - 1] + nums[i - 1];
135141
}
136-
f = new Integer[n][n];
137142
return dfs(0, n - 1);
138143
}
139144

140145
private int dfs(int i, int j) {
141-
if (i == j) {
146+
if (i >= j) {
142147
return 0;
143148
}
144149
if (f[i][j] != null) {
145150
return f[i][j];
146151
}
147-
int ans = 0;
148-
int a = 0;
152+
int ans = 0, l = 0, r = s[j + 1] - s[i];
149153
for (int k = i; k < j; ++k) {
150-
a += stoneValue[k];
151-
int b = s[j + 1] - s[i] - a;
152-
if (a < b) {
153-
if (ans >= a * 2) {
154+
l += nums[k];
155+
r -= nums[k];
156+
if (l < r) {
157+
if (ans > l * 2) {
154158
continue;
155159
}
156-
ans = Math.max(ans, a + dfs(i, k));
157-
} else if (a > b) {
158-
if (ans >= b * 2) {
160+
ans = Math.max(ans, l + dfs(i, k));
161+
} else if (l > r) {
162+
if (ans > r * 2) {
159163
break;
160164
}
161-
ans = Math.max(ans, b + dfs(k + 1, j));
165+
ans = Math.max(ans, r + dfs(k + 1, j));
162166
} else {
163-
ans = Math.max(ans, Math.max(a + dfs(i, k), b + dfs(k + 1, j)));
167+
ans = Math.max(ans, Math.max(l + dfs(i, k), r + dfs(k + 1, j)));
164168
}
165169
}
166170
return f[i][j] = ans;
@@ -177,35 +181,34 @@ public:
177181
int n = stoneValue.size();
178182
int s[n + 1];
179183
s[0] = 0;
180-
for (int i = 1; i <= n; ++i) {
181-
s[i] = s[i - 1] + stoneValue[i - 1];
184+
for (int i = 0; i < n; i++) {
185+
s[i + 1] = s[i] + stoneValue[i];
182186
}
183187
int f[n][n];
184-
memset(f, 0, sizeof(f));
185-
function<int(int, int)> dfs = [&](int i, int j) -> int {
186-
if (i == j) {
188+
memset(f, -1, sizeof(f));
189+
auto dfs = [&](this auto&& dfs, int i, int j) -> int {
190+
if (i >= j) {
187191
return 0;
188192
}
189-
if (f[i][j]) {
193+
if (f[i][j] != -1) {
190194
return f[i][j];
191195
}
192-
int ans = 0;
193-
int a = 0;
196+
int ans = 0, l = 0, r = s[j + 1] - s[i];
194197
for (int k = i; k < j; ++k) {
195-
a += stoneValue[k];
196-
int b = s[j + 1] - s[i] - a;
197-
if (a < b) {
198-
if (ans >= a * 2) {
198+
l += stoneValue[k];
199+
r -= stoneValue[k];
200+
if (l < r) {
201+
if (ans > l * 2) {
199202
continue;
200203
}
201-
ans = max(ans, a + dfs(i, k));
202-
} else if (a > b) {
203-
if (ans >= b * 2) {
204+
ans = max(ans, l + dfs(i, k));
205+
} else if (l > r) {
206+
if (ans > r * 2) {
204207
break;
205208
}
206-
ans = max(ans, b + dfs(k + 1, j));
209+
ans = max(ans, r + dfs(k + 1, j));
207210
} else {
208-
ans = max({ans, a + dfs(i, k), b + dfs(k + 1, j)});
211+
ans = max({ans, l + dfs(i, k), r + dfs(k + 1, j)});
209212
}
210213
}
211214
return f[i][j] = ans;
@@ -227,31 +230,34 @@ func stoneGameV(stoneValue []int) int {
227230
f := make([][]int, n)
228231
for i := range f {
229232
f[i] = make([]int, n)
233+
for j := range f[i] {
234+
f[i][j] = -1
235+
}
230236
}
231-
var dfs func(i, j int) int
237+
var dfs func(int, int) int
232238
dfs = func(i, j int) int {
233-
if i == j {
239+
if i >= j {
234240
return 0
235241
}
236-
if f[i][j] != 0 {
242+
if f[i][j] != -1 {
237243
return f[i][j]
238244
}
239-
ans, a := 0, 0
245+
ans, l, r := 0, 0, s[j+1]-s[i]
240246
for k := i; k < j; k++ {
241-
a += stoneValue[k]
242-
b := s[j+1] - s[i] - a
243-
if a < b {
244-
if ans >= a*2 {
247+
l += stoneValue[k]
248+
r -= stoneValue[k]
249+
if l < r {
250+
if ans > l*2 {
245251
continue
246252
}
247-
ans = max(ans, a+dfs(i, k))
248-
} else if a > b {
249-
if ans >= b*2 {
253+
ans = max(ans, dfs(i, k)+l)
254+
} else if l > r {
255+
if ans > r*2 {
250256
break
251257
}
252-
ans = max(ans, b+dfs(k+1, j))
258+
ans = max(ans, dfs(k+1, j)+r)
253259
} else {
254-
ans = max(ans, max(a+dfs(i, k), b+dfs(k+1, j)))
260+
ans = max(ans, max(dfs(i, k), dfs(k+1, j))+l)
255261
}
256262
}
257263
f[i][j] = ans
@@ -261,6 +267,49 @@ func stoneGameV(stoneValue []int) int {
261267
}
262268
```
263269

270+
#### TypeScript
271+
272+
```ts
273+
function stoneGameV(stoneValue: number[]): number {
274+
const n = stoneValue.length;
275+
const s: number[] = Array(n + 1).fill(0);
276+
for (let i = 0; i < n; i++) {
277+
s[i + 1] = s[i] + stoneValue[i];
278+
}
279+
const f: number[][] = Array.from({ length: n }, () => Array(n).fill(-1));
280+
281+
const dfs = (i: number, j: number): number => {
282+
if (i >= j) {
283+
return 0;
284+
}
285+
if (f[i][j] !== -1) {
286+
return f[i][j];
287+
}
288+
let [ans, l, r] = [0, 0, s[j + 1] - s[i]];
289+
for (let k = i; k < j; ++k) {
290+
l += stoneValue[k];
291+
r -= stoneValue[k];
292+
if (l < r) {
293+
if (ans > l * 2) {
294+
continue;
295+
}
296+
ans = Math.max(ans, l + dfs(i, k));
297+
} else if (l > r) {
298+
if (ans > r * 2) {
299+
break;
300+
}
301+
ans = Math.max(ans, r + dfs(k + 1, j));
302+
} else {
303+
ans = Math.max(ans, l + dfs(i, k), r + dfs(k + 1, j));
304+
}
305+
}
306+
return (f[i][j] = ans);
307+
};
308+
309+
return dfs(0, n - 1);
310+
}
311+
```
312+
264313
<!-- tabs:end -->
265314

266315
<!-- solution:end -->

0 commit comments

Comments
 (0)