What is the main pattern used in this problem?

The problem is best solved using state transition dynamic programming to enumerate all possible subexpression results efficiently.

How do I handle partial scoring for alternative evaluations?

Compute all possible outcomes of the expression using different operator orders and compare each student answer to this set for partial points.

Can I extend this approach to expressions with multi-digit numbers?

Yes, but you need to parse numbers correctly and ensure your DP memoization covers the expanded range of subexpressions.

What causes exponential time complexity here?

Without memoization, every subexpression is recomputed for each operator split, leading to exponential evaluations in the number of operators.

How does GhostInterview help with The Score of Students Solving Math Expression?

It provides step-by-step computation of all possible results, flags alternative evaluation paths, and calculates total student points efficiently using DP.

#2019

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

解出数学表达式的学生分数

给你一个字符串 s ，它只包含数字 0-9 ，加法运算符 '+' 和乘法运算符 '*' ，这个字符串表示一个合法的只含有个位数数字的数学表达式（比方说 3+5*2 ）。有 n 位小学生将计算这个数学表达式，并遵循如下运算顺序：按照从左到右的顺序计算乘法，然后按照从左到…

数组数学字符串动态规划栈

题目描述

给你一个字符串 s ，它只包含数字 0-9 ，加法运算符 '+' 和乘法运算符 '*' ，这个字符串表示一个合法的只含有 个位数数字的数学表达式（比方说 3+5*2）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序 ：

按照 从左到右 的顺序计算乘法，然后
按照 从左到右 的顺序计算加法。

给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下规则打分：

如果一位学生的答案等于表达式的正确结果，这位学生将得到 5 分。
否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到 2 分。
否则，这位学生将得到 0 分。

请你返回所有学生的分数和。

示例 1：

输入：s = "7+3*1*2", answers = [20,13,42]
输出：7
解释：如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,13,42] 。
一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10*1=10，10*2=20 。所以这位学生得分为 2 分：[20,13,42] 。
所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。

示例 2：

输入：s = "3+5*2", answers = [13,0,10,13,13,16,16]
输出：19
解释：表达式的正确结果为 13 ，所以有 3 位学生得到 5 分：[13,0,10,13,13,16,16] 。
学生可能通过错误的运算顺序得到结果 16 ：3+5=8，8*2=16 。所以两位学生得到 2 分：[13,0,10,13,13,16,16] 。
所有学生得分分别为：[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。

示例 3：

输入：s = "6+0*1", answers = [12,9,6,4,8,6]
输出：10
解释：表达式的正确结果为 6 。
如果一位学生通过错误的运算顺序计算该表达式，结果仍为 6 。
根据打分规则，运算顺序错误的学生也将得到 5 分（因为他们仍然得到了正确的结果），而不是 2 分。
所有学生得分分别为：[0,0,5,0,0,5] 。所有得分之和为 10 分。

提示：

3 <= s.length <= 31
s 表示一个只包含 0-9 ，'+' 和 '*' 的合法表达式。
表达式中所有整数运算数字都在闭区间 [0, 9] 以内。
1 <= 数学表达式中所有运算符数目（'+' 和 '*'） <= 15
测试数据保证正确表达式结果在范围 [0, 1000] 以内。
测试用例保证乘法中间步骤中的值永远不会超过 10⁹。
n == answers.length
1 <= n <= 10⁴
0 <= answers[i] <= 1000

lightbulb

解题思路

方法一：动态规划（区间 DP）

我们先设计一个函数 $cal(s)$ ，用于计算一个合法的只含有个位数数字的数学表达式的结果。那么正确答案就是 $x = cal(s)$ 。

我们记字符串 $s$ 的长度为 $n$ ，那么 $s$ 中的数字个数为 $m = \frac{n+1}{2}$ 。

我们定义 $f[i][j]$ 表示选择 $s$ 中的第 $i$ 个数字到第 $j$ 个数字（下标从 $0$ 开始）这一段数字，计算出的结果可能的取值。初始时 $f[i][i]$ 表示选择第 $i$ 个数字，结果只能是这个数字本身，即 $f[i][i] = \{s[i \times 2]\}$ （即第 $i$ 个数字映射到字符串 $s$ 中的下标为 $i \times 2$ 的字符）。

接下来，我们从大到小枚举 $i$ ，然后从小到大枚举 $j$ ，我们需要求出区间 $[i, j]$ 所有数字运算的结果可能的取值。我们在区间 $[i, j]$ 中枚举分界点 $k$ ，那么 $f[i][j]$ 可以由 $f[i][k]$ 和 $f[k+1][j]$ 通过运算符 $s[k \times 2 + 1]$ 得到。因此我们可以得到如下状态转移方程：

f[i][j] = \begin{cases} \{s[i \times 2]\}, & i = j \\ \bigcup\limits_{k=i}^{j-1} \{f[i][k] \otimes f[k+1][j]\}, & i < j \end{cases}

其中 $\otimes$ 表示运算符，即 $s[k \times 2 + 1]$ 。

那么字符串 $s$ 所有数字运算的结果可能的取值就是 $f[0][m-1]$ 。

最后，我们统计答案。我们用一个数组 $cnt$ 统计答案数组 $answers$ 中每个答案出现的次数。如果答案等于 $x$ ，那么这个学生得到 $5$ 分，否则如果答案在 $f[0][m-1]$ 中，那么这个学生得到 $2$ 分。遍历 $cnt$ ，统计答案即可。

时间复杂度 $O(n^3 \times M^2)$ ，空间复杂度 $O(n^2 \times M^2)$ 。其中 $M$ 是答案可能的最大值，而 $n$ 是字符串 $s$ 的长度中数字的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        def cal(s: str) -> int:
            res, pre = 0, int(s[0])
            for i in range(1, n, 2):
                if s[i] == "*":
                    pre *= int(s[i + 1])
                else:
                    res += pre
                    pre = int(s[i + 1])
            res += pre
            return res

        n = len(s)
        x = cal(s)
        m = (n + 1) >> 1
        f = [[set() for _ in range(m)] for _ in range(m)]
        for i in range(m):
            f[i][i] = {int(s[i << 1])}
        for i in range(m - 1, -1, -1):
            for j in range(i, m):
                for k in range(i, j):
                    for l in f[i][k]:
                        for r in f[k + 1][j]:
                            if s[k << 1 | 1] == "+" and l + r <= 1000:
                                f[i][j].add(l + r)
                            elif s[k << 1 | 1] == "*" and l * r <= 1000:
                                f[i][j].add(l * r)
        cnt = Counter(answers)
        ans = cnt[x] * 5
        for k, v in cnt.items():
            if k != x and k in f[0][m - 1]:
                ans += v << 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(4^k * n) where k is the number of operators, due to generating all possible subexpression evaluations. Space complexity is O(k^2) for memoization storage of subexpression results.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you considering operator precedence and all alternative evaluation orders?
question_mark
How are you memoizing intermediate results to prevent recomputation?
question_mark
Can you handle overlapping subexpressions efficiently using DP?

warning

常见陷阱

外企场景

error
Forgetting that students may apply operators in non-standard order, giving alternative valid results.
error
Recomputing subexpression values without memoization, causing exponential time.
error
Assuming all answers outside the correct one get zero points, ignoring partial scoring rules.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Expressions may include subtraction or division operators with similar scoring rules.
arrow_right_alt
Multiple-digit numbers instead of single-digit, requiring careful parsing.
arrow_right_alt
Changing point system to reward only top-k alternative answers instead of all.

help

常见问题

外企场景

继续练习

#1728 猫和老鼠 II #1569 将子数组重新排序得到同一个二叉搜索树的方案数 #1994 好子集的数目