题目链接：https://leetcode.cn/problems/the-score-of-students-solving-math-expression/description/
题目大意：给一个只含个位数和加号+和乘号*的数学表达式，以及一串学生们给出的答案。对于每个答案如果分数正确，加5分；如果错误，但是是因为搞错加法乘法的顺序的错误答案，加2分；其他答案0分。求这串答案的总分数。
思路：DP做，将一个表达式从某个operator中间分开，可能的结果就是左边的结果（operator）右边的结果。也就是说dp[i][j]的结果是所有dp[i][k] operator dp[k+2][j]的结果，其中operator = s[k+1]。
然而即使如此，也不一定能写对。因为每个基础的【可能的部分答案】是从【两个数和一个操作符】得来的，因此遍历时要先把所有长度为3的子串先遍历了，而不是单纯地枚举左右端点。在代码中的体现就是遍历的最外层从step == j-i开始。
for (int step = 2; step < N; step += 2) {for (int i = 0; i + step < N; i += 2) {for (int t = 0; t < step; t += 2) {for (auto x : dp[i][i+t]) {if (x == 0 && s[i+t+1] == '*') {dp[i][i+step].insert(0);continue;}for (auto y : dp[i+t+2][i+step]) {if (s[i+t+1] == '+') {if (x+y <= 1000)dp[i][i+step].insert(x+y);}else {if (x*y <= 1000)dp[i][i+step].insert(x*y);}}}}}}
得到所有可能的结果后，错误答案每个+2，正确答案每个+5即可。
完整代码
class Solution {
public:int calCorrect(string s) {stack<int> st;st.push(s[0] - '0');for (int i = 1; i < s.length(); i += 2) {if (s[i] == '+')st.push(s[i+1] - '0');elsest.top() *= (s[i+1] - '0');}int res = 0;while (!st.empty()) {res += st.top();st.pop();}return res;}int scoreOfStudents(string s, vector<int>& answers) {int cnt[1001] = {};for (auto num : answers)cnt[num]++;int correct = calCorrect(s);int N = s.length();vector<vector<unordered_set<int>>> dp(N+1, vector<unordered_set<int>>(N+1));for (int i = 0; i < N; i += 2)dp[i][i].insert(s[i] - '0');for (int step = 2; step < N; step += 2) {for (int i = 0; i + step < N; i += 2) {for (int t = 0; t < step; t += 2) {for (auto x : dp[i][i+t]) {if (x == 0 && s[i+t+1] == '*') {dp[i][i+step].insert(0);continue;}for (auto y : dp[i+t+2][i+step]) {if (s[i+t+1] == '+') {if (x+y <= 1000)dp[i][i+step].insert(x+y);}else {if (x*y <= 1000)dp[i][i+step].insert(x*y);}}}}}}int ans = cnt[correct] * 5;for (auto num : dp[0][N-1]) {if (num != correct)ans += 2 * cnt[num];}return ans;}
};