当前位置：首页 > 行业知识 > 【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目

行业知识

【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目

2026-10-19 03:34:17 来源：互联网转载

作者推荐

【动��规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II

本文涉及知识点

动态规划汇总

LeetCode1987:不同的好子序列数目

给你一个二进制字符串 binary 。 binary 的一个子序列如果是非空的且没有前导 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 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 operatorreturn m_iData

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>= 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’;

vector pre(2);

pre[1] = (binary[0] == ‘1’);

for (int i = 1; i

{

vector 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

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