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

2024-02-07 14:44
文章标签 算法 动态 规划 c++ 序列 不同 数目 1987 除重 好子

本文主要是介绍【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【状态压缩】【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 <= 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,i+1)。

动态规划的转移方程

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之和。

代码

template<int 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) {vector<C1097Int<>> pre(2);for (const auto& ch : binary){pre = {('0'==ch)? (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’;
vector<C1097Int<>> pre(2);
pre[1] = (binary[0] == ‘1’);
for (int i = 1; i < binary.size(); i++)
{
vector<C1097Int<>> 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 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/688046。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
2. c#从不同cs的文件调用函数

2. c#从不同cs的文件调用函数

1.文件目录如下： 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2