为公司建立网站,武邑网站建设公司,wordpress首页添加站点统计显示,wordpress 规则作者推荐
【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II
本文涉及知识点
动态规划汇总
LeetCode1987:不同的好子序列数目
给你一个二进制字符串 binary 。 binary 的一个 子序列 如果是 非空 的且没有 前导 0 #xff08;除非数字是 “0” 本身除非数字是 “0” 本身那么它就是一个 好 的子序列。 请你找到 binary 不同好子序列 的数目。 比方说如果 binary “001” 那么所有 好 子序列为 [“0”, “0”, “1”] 所以 不同 的好子序列为 “0” 和 “1” 。 注意子序列 “00” “01” 和 “001” 不是好的因为它们有前导 0 。 请你返回 binary 中 不同好子序列 的数目。由于答案可能很大请将它对 109 7 取余 后返回。 一个 子序列 指的是从原数组中删除若干个可以一个也不删除元素后不改变剩余元素顺序得到的序列。 示例 1 输入binary “001” 输出2 解释好的二进制子序列为 [“0”, “0”, “1”] 。 不同的好子序列为 “0” 和 “1” 。 示例 2 输入binary “11” 输出2 解释好的二进制子序列为 [“1”, “1”, “11”] 。 不同的好子序列为 “1” 和 “11” 。 示例 3 输入binary “101” 输出5 解释好的二进制子序列为 [“1”, “0”, “1”, “10”, “11”, “101”] 。 不同的好子序列为 “0” “1” “10” “11” 和 “101” 。 提示 1 binary.length 105 binary 只含有 ‘0’ 和 ‘1’ 。
动态规划
除0外不存在以0开始的子序列。如果存在0则必定存在子序列{0}。以下的分析排除{0}。 排除{0}后任意合法子序列在后面增加0或1都是合法子序列。
动态规划的状态表示
pre[0] 从binary[0,i)中选择若干字符形成以0结束的合法子序列数量。pre[1]以1结束的子序列数量。 dp和pre类似对应的是binary[0,i1)。
动态规划的转移方程
binary[i]为1 { p r e [ 0 ] 不选择当前字符以 0 结束的字符数量 情况一 p r e [ 1 ] 不选择当前字符以 1 结束的字符数 情况二 p r e [ 0 ] p r e [ 1 ] 1 选择当前字符以 1 结束的字符数量。 情况三 \begin{cases} pre[0] 不选择当前字符以0结束的字符数量 情况一 \\ pre[1] 不选择当前字符以1结束的字符数 情况二 \\ pre[0]pre[1]1 选择当前字符以1结束的字符数量。 情况三 \\ \end{cases} ⎩ ⎨ ⎧pre[0]pre[1]pre[0]pre[1]1不选择当前字符以0结束的字符数量不选择当前字符以1结束的字符数选择当前字符以1结束的字符数量。情况一情况二情况三 情况三又可以分三种情况 { p r e [ 0 ] 倒数第二个字符是 0 情况三一 p r e [ 1 ] 倒数第二个字符是 1 情况三二 1 子序列 1 。 情况三三 \begin{cases} pre[0] 倒数第二个字符是0 情况三一 \\ pre[1] 倒数第二个字符是1 情况三二 \\ 1 子序列{1}。 情况三三 \\ \end{cases} ⎩ ⎨ ⎧pre[0]pre[1]1倒数第二个字符是0倒数第二个字符是1子序列1。情况三一情况三二情况三三 情况一、情况二、情况三 内部不存在重复情况。 情况一以0结尾情况二、三以1结尾所以情况一和情况二三不会重复。 情况二所有的情况都和情况三重合情况二分类 { 倒数第二个字符是 0 被情况三一包含 倒数第二个字符是 1 被情况三二包含 子序列 1 。 和情况三三重复 \begin{cases} 倒数第二个字符是0 被情况三一包含 \\ 倒数第二个字符是1 被情况三二包含 \\ 子序列{1}。 和情况三三 重复\\ \end{cases} ⎩ ⎨ ⎧倒数第二个字符是0倒数第二个字符是1子序列1。被情况三一包含被情况三二包含和情况三三重复
总结 dp[1] pre[0]pre[1]1 dp[0] pre[0]
binary[i]为0
不能为子序列{0} dp[0] pre[0]pre[1] dp[1] pre[1]
动态规划的初始值
pre 全为0。
动态规划的返回值
pre之和。
代码
templateint MOD 1000000007
class C1097Int
{
public:C1097Int(long long llData 0) :m_iData(llData% MOD){}C1097Int operator(const C1097Int o)const{return C1097Int(((long long)m_iData o.m_iData) % MOD);}C1097Int operator(const C1097Int o){m_iData ((long long)m_iData o.m_iData) % MOD;return *this;}C1097Int operator-(const C1097Int o){m_iData (m_iData MOD - o.m_iData) % MOD;return *this;}C1097Int operator-(const C1097Int o){return C1097Int((m_iData MOD - o.m_iData) % MOD);}C1097Int operator*(const C1097Int o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int operator*(const C1097Int o){m_iData ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator(const C1097Int o)const{return m_iData o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet 1, iCur *this;while (n){if (n 1){iRet * iCur;}iCur * iCur;n 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData 0;;
};class Solution {
public:int numberOfUniqueGoodSubsequences(string binary) {vectorC1097Int pre(2);for (const auto ch : binary){pre {(0ch)? (pre[0] pre[1]):pre[0],(1 ch) ? (pre[0] pre[1]1) : pre[1] };}int iZero std::count(binary.begin(), binary.end(), 0) 0;return (pre[0] pre[1] iZero).ToInt();}
};2023年2月
class C1097Int { public: C1097Int(int iData 0) :m_iData(iData) { } C1097Int operator(const C1097Int o)const { return C1097Int(((long long)m_iData o.m_iData) % s_iMod); } C1097Int operator(const C1097Int o) { m_iData ((long long)m_iData o.m_iData) % s_iMod; return this; } C1097Int operator(const C1097Int o)const { return((long long)m_iData o.m_iData) % s_iMod; } C1097Int operator(const C1097Int o) { m_iData ((long long)m_iData *o.m_iData) % s_iMod; return *this; } bool operator(const C1097Int o)const { return m_iData o.m_iData; } C1097Int pow( int n)const { C1097Int iRet 1, iCur *this; while (n) { if (n 1) { iRet * iCur; } iCur * iCur; n 1; } return iRet; } C1097Int PowNegative1() { return pow(s_iMod - 2); } int ToInt()const { return m_iData; } private: int m_iData 0;; static const int s_iMod 1000000007; };
int operator(int iData, const C1097Int int1097) { int iRet int1097.operator(C1097Int(iData)).ToInt(); return iRet; }
int operator(int iData, const C1097Int int1097) { iData int1097.operator(C1097Int(iData)).ToInt(); return iData; }
int operator*(int iData, const C1097Int int1097) { int iRet int1097.operator*(C1097Int(iData)).ToInt(); return iRet; }
int operator*(int iData, const C1097Int int1097) { iData int1097.operator*(C1097Int(iData)).ToInt(); return iData; }
class Solution { public: int numberOfUniqueGoodSubsequences(string binary) { vector pre(2); for (const auto ch : binary) { vector dp(2); if (‘0’ ch) { pre[0] pre[1]; } else { pre[1] pre[0]; pre[1] 1; } } return (pre[0] pre[1] (int)(-1 ! binary.find(‘0’))).ToInt(); } };
2023年7月
class Solution { public: int numberOfUniqueGoodSubsequences(string binary) { bool bHasZero binary[0] ‘0’; vectorC1097Int pre(2); pre[1] (binary[0] ‘1’); for (int i 1; i binary.size(); i) { vectorC1097Int dp pre ; if (‘0’ binary[i]) { bHasZero true; dp[0] pre[0] pre[1]; } else { dp[1] pre[0] pre[1] 1; } pre.swap(dp); } return (C1097Int(bHasZero) pre[0] pre[1]).ToInt();
}};
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
