本文涉及知识点

动态规划汇总

字符串 表达式 栈

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

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

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

按照 从左到右 的顺序计算 加法 。

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

如果一位学生的答案 等于 表达式的正确结果，这位学生将得到 5 分。

否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到 2 分。

否则，这位学生将得到 0 分。

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

示例 1：

输入：s = “7+3 ⋆ \star ⋆ 1 ⋆ \star ⋆ 2”, answers = [20,13,42]

输出：7

解释：如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,13,42] 。

一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10 ⋆ \star ⋆ 1=10，10 ⋆ \star ⋆ 2=20 。所以这位学生得分为 2 分：[20,13,42] 。

所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。

示例 2：

输入：s = “3+5 ⋆ \star ⋆ 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 ⋆ \star ⋆ 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 ⋆ \star ⋆ 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] 以内。

n == answers.length

1 <= n <= 10⁴

0 <= answers[i] <= 1000

动态规划

num依次记录运算数，op依次记录运算符。利用栈实现一个简单的运算类，来计算正确结果。

利用动态规划来实现计算所有错误运算符的结果。

{ 正确结果为 [ 0 , 1000 ] 加上任意数只会不边或变大 乘以 0 以外的数，只会变大或不变 \begin{cases} 正确结果为[0,1000] \\ 加上任意数只会不边或变大\\ 乘以0以外的数，只会变大或不变\\ \end{cases} ⎩ ⎨ ⎧​正确结果为[0,1000]加上任意数只会不边或变大乘以0以外的数，只会变大或不变​ → \rightarrow → 中间结果>1001和1000完全一样 { 结果相同 乘了 0 大于 a n s w e r s 的最大值 1000 没有乘 0 \begin{cases} 结果相同 & 乘了0 \\ 大于answers的最大值1000 &没有乘0 \\ \end{cases} {结果相同大于answers的最大值1000​乘了0没有乘0​

动态规划的状态表示

dp[len][i]表示num[i,i+len)所有运算顺序正确或错误可能的结果。

动态规划的转移方程

dp[len][i] = 追加 l e n 1 : 1 l e n − 1 _{len1:1}^{len-1} len1:1len−1​dp[len1][i] 加（或乘) dp[len-len1][i+len1]

动态规划的初始值

dp[1][i] = num[i]

动态规划的填表顺序

len 从2到大，以确保填表顺序。

i从小到大。

动态规划的返回值

正确结果得5分，dp.back()[0]中的值得2分。

代码

核心代码

class Solution {
public:
	int scoreOfStudents(string s, vector& answers) {
		CExpression exp;
		for (const char& ch : s)
		{
			if (('+' == ch) || ('*' == ch))
			{
				exp.AddOpe(ch);
			}
			else
			{
				exp.AddNum(ch - '0');
			}
		}
		const int iAns = exp.DoAddSub();
		int num[16];
		char ope[15];
		for (int i = 0; i < s.length(); i++)
		{
			if (i & 1)
			{
				ope[i / 2] = s[i];
			}
			else
			{
				num[i / 2] = s[i] - '0';
			}
		}
		int n = (s.length() + 1) / 2;
		vector >> dp(n+1, vector>(n));
		for (int i = 0; i < n; i++)
		{
			dp[1][i].emplace(num[i]);
		}
		for (int len = 2; len <= n; len++)
		{
			for (int i = 0; i + len <= n; i++)
			{
				for (int len1 = 1; len1 < len; len1++)
				{
					for (const auto& n1 : dp[len1][i])
					{
						for (const auto& n2 : dp[len - len1][i + len1])
						{
							const int ret = ('+' == ope[i + len1 - 1]) ? (n1 + n2) : (n1 * n2);
							dp[len][i].emplace((ret>1001)?1001:ret);
						}
					}
				}
			}
		}
		int iRet = 0;
		for (const auto& ans : answers)
		{
			if (iAns == ans)
			{
				iRet += 5;
			}
			else if (dp.back()[0].count(ans))
			{
				iRet += 2;
			}
		}
		return iRet;
	}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}
int main()
{	
	string s;
	vector answers;
	{
		Solution sln;
		s = "7+3*1*2", answers = { 20, 13, 42 };
		auto res = sln.scoreOfStudents(s,answers);
		Assert(res,7);
	}
	{
		Solution sln;
		s = "3+5*2", answers = { 13, 0, 10, 13, 13, 16, 16 };
		auto res = sln.scoreOfStudents(s, answers);
		Assert(res, 19);
	}
	{
		Solution sln;
		s = "6+0*1", answers = { 12, 9, 6, 4, 8, 6 };
		auto res = sln.scoreOfStudents(s, answers);
		Assert(res, 10);
	}
}

2023年2月版

class Solution {

public:

int scoreOfStudents(string s, vector& answers) {

m_c = s.length();

const int iVilid = GetVilidAns(s);

vector < vector> vLenPosErrAns(m_c + 1, vector(m_c));

for (int len = 1; len <= m_c; len += 2)

{

for (int iPos = 0; iPos+len-1 < m_c; iPos += 2)

{

if (1 == len)

{

vLenPosErrAns[len][iPos].insert(s[iPos] - ‘0’);

continue;

}

for (int leftLen = 1;; leftLen += 2)

{

const int iRightLen = len - 1 - leftLen;

if (iRightLen <= 0)

{

break;

}

CalSet(vLenPosErrAns[len][iPos], vLenPosErrAns[leftLen][iPos], s[iPos + leftLen], vLenPosErrAns[iRightLen][iPos + leftLen + 1]);

}

}

}

int iRet = 0 ;

for (int i = 0; i < answers.size(); i++)

{

if (iVilid == answers[i])

{

iRet += 5;

continue;

}

if (vLenPosErrAns[m_c][0].count(answers[i]))

{

iRet += 2;

}

}

return iRet;

}

void CalSet(std::unordered_set& setResult, const std::unordered_set& set1, char chOpe, const std::unordered_set& set2)

{

for (auto it : set1)

{

for (auto ij : set2)

{

int iResult = it + ij;

if (‘’ == chOpe )

{

iResult = itij;

}

if (iResult <= 1000)

{

setResult.insert(iResult);

}

}

}

}

int GetVilidAns(string s)

{

stack staNum;

stack staOpe;

for (const auto& ch : s)

{

if ((’’ == ch) || (‘+’ == ch))

{

staOpe.push(ch);

}

else

{

staNum.push(ch-‘0’);

if ((staNum.size() >= 2) && staOpe.size()&&(''== staOpe.top()))

{

int t1 = staNum.top();

staNum.pop();

int t2 = staNum.top();

staNum.pop();

staNum.push(t1*t2);

staOpe.pop();

}

}

}

	 while (staNum.size() >= 2)
	 {
		 int t1 = staNum.top();
		 staNum.pop();
		 int t2 = staNum.top();
		 staNum.pop();
		 staNum.push(t1+t2);
		 staOpe.pop();
	 }
	 return staNum.top();
 }
 int m_c;

};

2023年7月

class Solution {

public:

int scoreOfStudents(string s, vector& answers) {

for (const auto& ch : s)

{

if ((‘+’ == ch) || (‘’ == ch))

{

m_staOpes.emplace(ch);

}

else

{

const int iNum = ch - ‘0’;

if (m_staOpes.size() && ('’ == m_staOpes.top()))

{

const int iPre = m_staNums.top();

m_staNums.pop();

m_staNums.emplace(iPre * iNum);

m_staOpes.pop();

}

else

{

m_staNums.emplace(iNum);

}

}

}

while (m_staOpes.size())

{

int iNext = m_staNums.top();

m_staNums.pop();

const int iPre = m_staNums.top();

m_staNums.pop();

m_staOpes.pop();

m_staNums.emplace(iPre + iNext);

}

m_c = s.length() / 2 + 1;

m_dp.assign(m_c, vector(m_c));

for (int i = 0; i < m_c; i++)

{

m_dp[i][i] .emplace( s[i * 2] - ‘0’);

}

for (int len = 2; len <= m_c; len++)

{

#define END (begin + len - 1)

for (int begin = 0; END < m_c; begin++)

{

for (int mid = begin ; mid < END; mid++)

{

Ope(m_dp[begin][END], m_dp[begin][mid], m_dp[mid + 1][END],s[mid*2+1]);

}

}

}

int iScore = 0;

for (const auto& ans : answers)

{

if (ans == m_staNums.top())

{

iScore += 5;

}

else if (m_dp[0].back().count(ans))

{

iScore += 2;

}

}

return iScore;

}

void Ope(set& res, const set& pre, const set& next,const char& ch )

{

for (const auto& it : pre)

{

for (const auto& ij : next)

{

int iRes = (‘+’ == ch) ? (it + ij) : (it * ij);

if (iRes > 1000)

{

break;

}

res.emplace(iRes);

}

}

if (res.empty())

{

res.emplace(1001);

}

}

stack m_staNums;

stack m_staOpes;

int m_c;

vector> m_dp;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。