This problem looks busy at first, but the accepted solution is built around one steady invariant. For 1563. Stone Game V, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, dynamic programming, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- dfs + memorization, using unordered_map
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are stoneGameV.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//dfs + memorization, using unordered_map
02//Runtime: 1424 ms, faster than 12.50% of C++ online submissions for Stone Game V.
03//Memory Usage: 34.6 MB, less than 12.50% of C++ online submissions for Stone Game V.
04struct pair_hash_int {
05 inline std::size_t operator()(const std::pair<int,int> & v) const {
06 return v.first*31+v.second;
07 }
08};
09
10class Solution {
11public:
12 unordered_map<pair<int, int>, int, pair_hash_int> memo;
13
14 int stoneGameV(vector<int>& stoneValue, int start = -1, int end = -1) {
15 int score = 0;
16 if(start == -1) start = 0;
17 if(end == -1) end = stoneValue.size();
18 if(end-start <= 1) return score;
19
20 if(memo.find({start, end}) != memo.end()){
21 return memo[{start, end}];
22 }
23
24 int sum = accumulate(stoneValue.begin()+start, stoneValue.begin()+end, 0);
25 int leftsum = 0;
26
27 //left part: [0...i]
28 for(int i = start; i < end; ++i){
29 leftsum += stoneValue[i];
30
31 if(leftsum > sum-leftsum){
32 //discard left
33 //remain [pos+1...]
34 // cout << "add " << sum-leftsum << endl;
35 score = max(score, sum-leftsum + stoneGameV(stoneValue, i+1, end));
36 }else if(leftsum < sum-leftsum){
37 //discard right
38 //remain [0...pos]
39 // cout << "add " << leftsum << endl;
40 score = max(score, leftsum + stoneGameV(stoneValue, start, i+1));
41 }else{
42 //leftsum == sum-leftsum
43 int leftres = stoneGameV(stoneValue, start, i+1);
44 int rightres = stoneGameV(stoneValue, i+1, end);
45 // cout << "add " << leftsum << endl;
46 score = max(score, leftsum + max(leftres, rightres));
47 }
48 }
49
50 return memo[{start, end}] = score;
51 }
52};
53
54//dfs + memorization, using 2d array rather than unordered_map for speed up
55//Runtime: 204 ms, faster than 37.50% of C++ online submissions for Stone Game V.
56//Memory Usage: 10.7 MB, less than 50.00% of C++ online submissions for Stone Game V.
57class Solution {
58public:
59 int memo[501][501];
60
61 int stoneGameV(vector<int>& stoneValue, int start, int end) {
62 int score = 0;
63 if(start == -1) start = 0;
64 if(end == -1) end = stoneValue.size();
65 if(end-start <= 1) return score;
66
67 if(memo[start][end] != -1){
68 return memo[start][end];
69 }
70
71 int sum = accumulate(stoneValue.begin()+start, stoneValue.begin()+end, 0);
72 int leftsum = 0;
73
74 //left part: [0...i]
75 for(int i = start; i < end; ++i){
76 leftsum += stoneValue[i];
77
78 if(leftsum > sum-leftsum){
79 //discard left
80 //remain [pos+1...]
81 // cout << "add " << sum-leftsum << endl;
82 score = max(score, sum-leftsum + stoneGameV(stoneValue, i+1, end));
83 }else if(leftsum < sum-leftsum){
84 //discard right
85 //remain [0...pos]
86 // cout << "add " << leftsum << endl;
87 score = max(score, leftsum + stoneGameV(stoneValue, start, i+1));
88 }else{
89 //leftsum == sum-leftsum
90 int leftres = stoneGameV(stoneValue, start, i+1);
91 int rightres = stoneGameV(stoneValue, i+1, end);
92 // cout << "add " << leftsum << endl;
93 score = max(score, leftsum + max(leftres, rightres));
94 }
95 }
96
97 return memo[start][end] = score;
98 }
99
100 int stoneGameV(vector<int>& stoneValue) {
101 memset(&memo[0][0], -1, sizeof(memo));
102 return stoneGameV(stoneValue, -1, -1);
103 }
104};
105
106//dfs + memorization, using 2d array rather than unordered_map for speed up, prefix sum
107//https://leetcode.com/problems/stone-game-v/discuss/806723/C%2B%2B-Prefix-Sum-%2B-DP-(Memoization)
108//Runtime: 328 ms, faster than 37.50% of C++ online submissions for Stone Game V.
109//Memory Usage: 11.3 MB, less than 50.00% of C++ online submissions for Stone Game V.
110class Solution {
111public:
112 int memo[501][501];
113 vector<int> prefixSum;
114
115 int stoneGameV(vector<int>& stoneValue, int start, int end) {
116 int score = 0;
117 if(end-start <= 1) return score;
118
119 if(memo[start][end] != -1){
120 return memo[start][end];
121 }
122
123 int leftsum, rightsum;
124
125 //left part: [start...i], right part: [i+1...end)
126 for(int i = start; i < end; ++i){
127 //[start...i]
128 //prefixSum[i+1]: [0...i]
129 //prefixSum[start]: [0...start-1]
130 leftsum = prefixSum[i+1] - prefixSum[start];
131 //[i+1...end)
132 //prefixSum[end]: [0...end)
133 //prefixSum[i+1]: [0...i]
134 rightsum = prefixSum[end] - prefixSum[i+1];
135
136 if(leftsum > rightsum){
137 //discard left
138 //remain [pos+1...]
139 // cout << "add " << sum-leftsum << endl;
140 score = max(score, rightsum + stoneGameV(stoneValue, i+1, end));
141 }else if(leftsum < rightsum){
142 //discard right
143 //remain [0...pos]
144 // cout << "add " << leftsum << endl;
145 score = max(score, leftsum + stoneGameV(stoneValue, start, i+1));
146 }else{
147 //leftsum == rightsum
148 int leftres = stoneGameV(stoneValue, start, i+1);
149 int rightres = stoneGameV(stoneValue, i+1, end);
150 // cout << "add " << leftsum << endl;
151 score = max(score, leftsum + max(leftres, rightres));
152 }
153 }
154
155 return memo[start][end] = score;
156 }
157
158 int stoneGameV(vector<int>& stoneValue) {
159 memset(&memo[0][0], -1, sizeof(memo));
160
161 int n = stoneValue.size();
162 prefixSum = vector<int>(n+1, 0);
163 for(int i = 0; i < n; ++i){
164 prefixSum[i+1] = prefixSum[i] + stoneValue[i];
165 }
166
167 return stoneGameV(stoneValue, 0, n);
168 }
169};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.