python3 解法, 执行用时: 1816 ms, 内存消耗: 17.9 MB, 提交时间: 2023-09-18 11:27:10

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        target=eval(s)
        print(target)
        n=len(s)
        # dp[l][r]表示区间[l,r]能通过不同顺序计算出的结果
        dp=defaultdict(lambda:defaultdict(set))
        for i in range(0,n,2):
            dp[i][i].add(int(s[i]))
        
        
        for span in range(3,n+1,2):
            for l in range(0,n-span+1,2):
                r=l+span-1
                for mid in range(l+1,r,2):
                    v1=dp[l][mid-1]
                    v2=dp[mid+1][r]
                    for a in v1:
                        for b in v2:
                            if s[mid]=='*' and a*b<=1000:
                                dp[l][r].add(a*b)
                            if s[mid]=='+' and a+b<=1000:
                                dp[l][r].add(a+b)
        
        res=0
        for a in answers:
            if a==target:
                res+=5
            elif a in dp[0][n-1]:
                res+=2
        return res

cpp 解法, 执行用时: 620 ms, 内存消耗: 180.1 MB, 提交时间: 2023-09-18 11:26:27

class Solution {
public:
    int scoreOfStudents(string s, vector<int>& answers) {
        // Step 1：统计所有学生答案
        // 所有学生答案都在[0, 1000]，因此开一个差不多大小的空间即可
        vector<int> count(1024);
        for(auto p : answers){
            count[p]++;
        }
        
        // Step 2：计算正确结果
                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');
            }
            else{ // 乘法运算，直接做
                st.top() *= (s[i + 1] - '0');
            }
        }
        // 弹栈，计算所有加法运算
        int right = 0;
        while(st.size() > 0){
            right += st.top();
            st.pop();
        }
        // 正确的得分 = 5 * 正确人数
        int ans = 5 * count[right];
        
        // Step 3：枚举所有可能结果
        // 开空间，dp为n*n的数组，每一项为一个集合
        int len = s.length();
        vector<vector<unordered_set<int>>> dp(len + 2, vector<unordered_set<int>>(len + 2));
        // 初始化，对于i=j情况，能组成的值为其本身
        for(int j = 0; j < len; j += 2){
            dp[j][j].insert(s[j] - '0');
        }
        // 枚举步伐，不断增大，即 step = j-i
        for(int step = 2; step < len; step += 2){
            // 枚举开始位置 i
            for(int i = 0; i + step < len; i += 2){
                // 枚举左半部分长度 t
                for(int t = 0; t < step; t += 2){
                    // x是左半部分所有可能值
                    // y是右半部分所有可能值
                    for(auto x : dp[i][i + t]){
                        for(auto y : dp[i + t + 2][i + step]){
                            // 根据中间连接符是+/*，来计算连接后的值
                            if(s[i + t + 1] == '+'){
                                // 因为学生猜测结果均在 [0,1000]，因此超限的值可以直接忽略。
                                if(x + y <= 1000)
                                dp[i][i + step].insert(x + y);
                            }
                            else{
                                if(x * y <= 1000)
                                dp[i][i + step].insert(x * y);
                            }
                        }
                    }
                }
            }
        }
        // Step 4：统计顺序错误同学得分
        for(auto p : dp[0][len - 1]){
            if(p != right){ // 只有错误答案需要统计，防止二次统计正确同学
	            ans += 2 * count[p];
	        }
	    }
        return ans;
    }
};

golang 解法, 执行用时: 616 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-18 11:24:35

func scoreOfStudents(s string, answers []int) (ans int) {
	n := len(s)
	// 计算正确答案
	correct := 0
	for i := 0; i < n; {
		mul := int(s[i] & 15)
		for i += 2; i < n && s[i-1] == '*'; i += 2 {
			mul *= int(s[i] & 15)
		}
		correct += mul
	}

	// 区间 DP
	// dp[l][r] 表示 s[l..r] 内的表达式在不同计算顺序下的不超过 1000 的所有可能值
	dp := make([][]map[int]bool, n)
	for i := range dp {
		dp[i] = make([]map[int]bool, n)
	}
	var f func(int, int) map[int]bool
	f = func(l, r int) map[int]bool {
		if l == r {
			return map[int]bool{int(s[l] & 15): true}
		}
		if dp[l][r] != nil {
			return dp[l][r]
		}
		res := map[int]bool{}
		for i := l + 1; i < r; i += 2 { // 枚举分界点
			for v := range f(l, i-1) { // 计算左边表达式的可能值
				for w := range f(i+1, r) { // 计算右边表达式的可能值
					x := v + w
					if s[i] == '*' {
						x = v * w
					}
					if x <= 1000 { // 超过 1000 的结果不计入
						res[x] = true
					}
				}
			}
		}
		dp[l][r] = res
		return res
	}
	res := f(0, n-1)
	for _, v := range answers {
		if v == correct {
			ans += 5
		} else if res[v] {
			ans += 2
		}
	}
	return
}