Formatted question description: https://leetcode.ca/all/2019.html

# 2019. The Score of Students Solving Math Expression (Hard)

You are given a string `s`

that contains digits `0-9`

, addition symbols `'+'`

, and multiplication symbols `'*'`

**only**, representing a **valid** math expression of **single digit numbers** (e.g., `3+5*2`

). This expression was given to `n`

elementary school students. The students were instructed to get the answer of the expression by following this **order of operations**:

- Compute
**multiplication**, reading from**left to right**; Then, - Compute
**addition**, reading from**left to right**.

You are given an integer array `answers`

of length `n`

, which are the submitted answers of the students in no particular order. You are asked to grade the `answers`

, by following these **rules**:

- If an answer
**equals**the correct answer of the expression, this student will be rewarded`5`

points; - Otherwise, if the answer
**could be interpreted**as if the student used the**incorrect order of operations**,**once**or**multiple**times, this student will be rewarded`2`

points; - Otherwise, this student will be rewarded
`0`

points.

Return *the sum of the points of the students*.

**Example 1:**

Input:s = "7+3*1*2", answers = [20,13,42]Output:7Explanation:As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,,42] A student might have used this incorrect order of operations: 7+3=10, 10*1=10, 10*2=20. Therefore one student is rewarded 2 points: [13,13,42] The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.20

**Example 2:**

Input:s = "3+5*2", answers = [13,0,10,13,13,16,16]Output:19Explanation:The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [,0,10,13,13,16,16] A student might have used this incorrect order of operations: 3+5=8, 8*2=16. Therefore two students are rewarded 2 points: [13,0,10,13,13,13,16] The points for the students are: [5,0,0,5,5,2,2]. The sum of the points is 5+0+0+5+5+2+2=19.16

**Example 3:**

Input:s = "6+0*1", answers = [12,9,6,4,8,6]Output:10Explanation:The correct answer of the expression is 6. If a student had used some incorrect order of operations, the answer would also be 6. By the rules of grading, the students will still be rewarded 5 points (as they got the correct answer), not 2 points. The points for the students are: [0,0,5,0,0,5]. The sum of the points is 10.

**Constraints:**

`3 <= s.length <= 31`

`s`

represents a valid expression that contains only digits`0-9`

,`'+'`

, and`'*'`

only.- All the integer operands in the expression are in the
**inclusive**range`[0, 9]`

. `1 <=`

The count of all operators (`'+'`

and`'*'`

) in the math expression`<= 15`

- Test data are generated such that the correct answer of the expression is in the range of
`[0, 1000]`

. `n == answers.length`

`1 <= n <= 10`

^{4}`0 <= answers[i] <= 1000`

**Similar Questions**:

## Solution 1. DP

Let `dp[i][j]`

be the possible values the students can get using `s[i..j]`

.

```
dp[i][i] = { s[i] - '0' }
```

For `dp[i][j]`

, we enumerate all the indexes `k`

of the operators between `i`

and `j`

. Let `a`

and `b`

be elements in `dp[i][k-1]`

and `dp[k+1][j]`

.

- If
`s[k] == '+'`

, we insert`a + b`

into`dp[i][j]`

- If
`s[k] == '*'`

, we insert`a * b`

into`dp[i][j]`

Bottom-up DP:

```
// OJ: https://leetcode.com/problems/the-score-of-students-solving-math-expression/
// Time: O(N^3 * 1000^2)
// Space: O(N^2 * 1000)
class Solution {
public:
int eval(string &s, int first, int last) {
if (first == last) return s[first] - '0';
int i = first + 1;
for (; i <= last && s[i] == '*'; i += 2); // find the first '+'
if (i <= last) return eval(s, first, i - 1) + eval(s, i + 1, last); // calculate the first '+'
int ans = 1;
for (int i = first; i <= last; i += 2) ans *= s[i] - '0';
return ans; // If there is no `+`, calculate all the `*`s
}
int scoreOfStudents(string s, vector<int>& A) {
int ans = 0, N = s.size(), correct = eval(s, 0, N - 1);
unordered_set<long long> dp[32][32];
for (int i = 0; i < N; i += 2) dp[i][i].insert(s[i] - '0');
for (int i = N - 3; i >= 0; i -= 2) {
for (int j = i + 2; j < N; j += 2){
for (int k = i + 1; k < j; k += 2) { // For s[i..j], enumerate every operators' indexes `k`
for (auto a : dp[i][k - 1]) {
for (auto b : dp[k + 1][j]) {
int val = s[k] == '+' ? a + b : a * b;
if (val <= 1000) dp[i][j].insert(val);
}
}
}
}
}
for (int n : A) {
if (n == correct) ans += 5;
else if (dp[0][N - 1].count(n)) ans += 2;
}
return ans;
}
};
```

Or Top-down DP:

```
// OJ: https://leetcode.com/problems/the-score-of-students-solving-math-expression/
// Time: O(N^3 * 1000^2)
// Space: O(N^2 * 1000)
class Solution {
int eval(string &s, int first, int last) {
if (first == last) return s[first] - '0';
auto it = find(begin(s) + first, begin(s) + last + 1, '+');
if (it == begin(s) + last + 1) {
int ans = 1;
for (int j = first; j <= last; j += 2) ans *= s[j] - '0';
return ans;
}
return eval(s, first, it - begin(s) - 1) + eval(s, it - begin(s) + 1, last);
}
unordered_set<int> m[32][32] = {};
unordered_set<int> *dp(string &s, int first, int last) {
if (m[first][last].size()) return &m[first][last];
for (int i = first + 1; i < last; i += 2) {
for (int a : *dp(s, first, i - 1)) {
for (int b : *dp(s, i + 1, last)) {
int val = s[i] == '+' ? a + b : a * b;
if (val <= 1000) m[first][last].insert(val);
}
}
}
return &m[first][last];
}
public:
int scoreOfStudents(string s, vector<int>& A) {
int correct = eval(s, 0, s.size() - 1), ans = 0;
for (int i = 0; i < s.size(); i += 2) m[i][i].insert(s[i] - '0');
auto all = dp(s, 0, s.size() - 1);
for (int n : A) {
if (n == correct) ans += 5;
else if (all->count(n)) ans += 2;
}
return ans;
}
};
```