无锡建设局网站一号通,动漫制作专业个人简历,企业只有建立自己的网站平台,网站生成静态页面工具作者推荐
【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数
本文涉及知识点
动态规划汇总
LeetCode1388 3n 块披萨
给你一个披萨#xff0c;它由 3n 块不同大小的部分组成#xff0c;现在你和你的朋友们需要按照如下规则来分披萨#xff1a; 你挑选 任…作者推荐
【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数
本文涉及知识点
动态规划汇总
LeetCode1388 3n 块披萨
给你一个披萨它由 3n 块不同大小的部分组成现在你和你的朋友们需要按照如下规则来分披萨 你挑选 任意 一块披萨。 Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。 Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。 重复上述过程直到没有披萨剩下。 每一块披萨的大小按顺时针方向由循环数组 slices 表示。 请你返回你可以获得的披萨大小总和的最大值。 示例 1 输入slices [1,2,3,4,5,6] 输出10 解释选择大小为 4 的披萨Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 6 10 。 示例 2 输入slices [8,9,8,6,1,1] 输出16 解释两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨你的朋友们就会选择大小为 8 的披萨这种情况下你的总和不是最大的。 提示 1 slices.length 500 slices.length % 3 0 1 slices[i] 1000
动态规划
原理
题目等效于以下描述 从[0,3n)中选择n个不相邻的数据注意0和3n-1是相邻。 题目一定符合描述 因为相邻的数被Alice Bob 取走了。 描述一定符合题意证明如下 a,n1只有一个数必定不相邻。 b,n 1 。必定有两个选取的数之间有两个或以上的数。反证法如果任何两个选取的数之间都只有一个数那数的总数量是2n和3n矛盾。对勾表示选取X表示没选取。 ⋯ X ✓ X ‾ X ✓ X ⋯ \cdots \underline{ X \checkmark X} X \checkmark X \cdots ⋯X✓XX✓X⋯ 我们将下划线部分删除变成 ⋯ X ✓ X ⋯ \cdots X \checkmark X \cdots ⋯X✓X⋯ 仍然符合描述但n减少了1。不断迭代n当n为1时证明成立。
动态规划的状态表示
pre[b1][b2][k] 表示[0,i)中选取了k个数的最大值b1是否选择了i-1b2是否选择了0。 dp类似表示[0,i1)的情况。
动态规划的转移方程
当前数 没选择。 b1 变成0。其它不变。 下面分析选取的情况 b11true b21b2 k1k1 k的取值范围:[0,n-1) dp[b11][b21][k1] max( ⋯ \cdots ⋯,pre[b1][b2][k]arr[i]) 如果b1等于true忽略。如果i为3n-1且b2忽略。
动态规划的初始值
pre[1][1][1] arr[0] pre[0][0][0] 0 其它 -1e6表示非法状态
动态规划的填表顺序
i从1到3n-1
动态规划的返回值
max(dp[0][0].back() dp[0][1].back(),dp[1][0].back()dp[1][1].back())
代码
核心代码
class Solution {
public:int maxSizeSlices(vectorint slices) {const int n3 slices.size();const int n n3 / 3;vectorvectorvectorint pre(2, vectorvectorint(2, vectorint(n 1, m_iNotMay)));pre[1][1][1] slices[0];pre[0][0][0] 0;for (int i 1; i n3; i){vectorvectorvectorint dp(2, vectorvectorint(2, vectorint(n 1, m_iNotMay)));//不选择slices[i]for (int i2 0; i2 2; i2){for (int i3 0; i3 n; i3){dp[0][i2][i3] max(pre[0][i2][i3], pre[1][i2][i3]);}}//选择{for (int i3 0; i3 n; i3){dp[1][0][i31] max(dp[1][0][i31], pre[0][0][i3] slices[i]);}}if (n3 - 1 ! i){for (int i3 0; i3 n; i3){dp[1][1][i31] max(dp[1][1][i31], pre[0][1][i3] slices[i]);}}pre.swap(dp);}vectorint vMax { pre[0][0].back(), pre[0][1].back(),pre[1][0].back(),pre[1][1].back() };return *std::max_element(vMax.begin(), vMax.end());}const int m_iNotMay -1000000;
};测试用例
int main()
{ vectorint slices;int d;{Solution sln;slices { 1, 2, 3, 4, 5, 6 };auto res sln.maxSizeSlices(slices);Assert(10, res);}{Solution sln;slices { 8,9,8,6,1,1 };auto res sln.maxSizeSlices(slices);Assert(16, res);}{Solution sln;slices { 9,5,1,7,8,4,4,5,5,8,7,7 };auto res sln.maxSizeSlices(slices);Assert(30, res);}{Solution sln;slices { 10,9,1,10,8,5,10,2,2 };auto res sln.maxSizeSlices(slices);Assert(30, res);}{Solution sln;slices { 4,1,2,5,8,3,1,9,7 };auto res sln.maxSizeSlices(slices);Assert(21, res);}
}
优化
关于0和3n-1不能同时选择的解决方法 情况一选择了0没有选择3n-1。 情况二选择了3n-1没有选择0。 情况三两者都没选择。
只处理slices的前3n-1个元素可以枚举所有的情况一和情况三。 值处理slices的后3n-1个元素可以枚举所有的情况一和情况三。
class Solution {
public:int maxSizeSlices(vectorint slices) {const int n3 slices.size();const int n n3 / 3;return max(Do(slices.data(),n3-1,n), Do(slices.data()1, n3 - 1, n));}int Do(int* slices, int len, int n){vectorvectorint pre(2, vectorint(n 1, m_iNotMay));pre[0][0] 0;pre[1][1] slices[0];for (int i 1; i len; i){vectorvectorint dp(2, vectorint(n 1, m_iNotMay)); for (int i2 0; i2 n; i2){//不选择dp[0][i2] max(pre[0][i2], pre[1][i2]);}for (int i2 0; i2 n; i2){dp[1][i21] max(pre[1][i21], pre[0][i2]slices[i]);}pre.swap(dp);}return max(pre[0].back(), pre[1].back());}const int m_iNotMay -1000000;
};2023年2月版
class Solution { public: int maxSizeSlices(vector slices) { m_c slices.size(); vectorvector dp(m_c/31,vector(m_c)); { for (int i 0; i m_c; i) { dp[1][i] slices[GetIndex(i 1)]; } } for (int len 6; len m_c; len 3) { for (int iPos 0; iPos m_c; iPos) { int iMaxValue 0; //可以拆分2个 for (int j 3; j len; j 3) { int iVaue dp[j/3][iPos] dp[(len-j) / 3][GetIndex( iPosj)]; iMaxValue max(iMaxValue, iVaue); } //消除两端元素和中间元素 for (int j 1; j len; j3 ) { int iVaue slices[GetIndex(iPos j)] dp[(j - 1) / 3][GetIndex(iPos 1)]; const int iRightLen (len - j -2 ) / 3; if ( iRightLen 0 ) { iVaue dp[iRightLen][GetIndex(iPos j 1)]; } iMaxValue max(iMaxValue, iVaue); } dp[len / 3][iPos] iMaxValue; } } auto pre dp[m_c / 3]; return *std::max_element(pre.begin(), pre.end()); } int GetIndex(int index) { return (index m_c)%m_c; } int m_c; };
2023年8月版
class Solution { public: int maxSizeSlices(vector slices) { needSel slices.size() / 3; vectorvectorvector pre(2, vectorvector(2, vector(needSel1, -1000 * 1000))); pre[0][0][0] 0; //pre[i][j][k] i是否选择第0个元素j前一个元素是否被选择已经选择了多少个 for (int i 0; i slices.size(); i) { vectorvectorvector dp(2, vectorvector(2, vector(needSel 1, -1000 * 1000))); for (auto sel0 0; sel0 2; sel0) { for (auto selPre 0; selPre 2; selPre) { for (int hasSel 0; hasSel needSel; hasSel) { //不选择 dp[sel0][0][hasSel] max(dp[sel0][0][hasSel],pre[sel0][selPre][hasSel]); //选择 bool bCanSel (hasSel needSel) (!selPre); if (sel0 (i 1 slices.size())) { bCanSel false; } if (bCanSel) { bool sel0cur sel0 || (0 i); dp[sel0cur][1][hasSel1] max(dp[sel0cur][1][hasSel 1], pre[sel0][selPre][hasSel] slices[i]); } } } } pre.swap(dp); } int iMax 0; for (auto sel0 0; sel0 2; sel0) { for (auto selPre 0; selPre 2; selPre) { iMax max(iMax, pre[sel0][selPre].back()); } } return iMax; } int needSel; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
