数学研发论坛

 找回密码
 欢迎注册
查看: 639|回复: 0

[讨论] 动态规划与最大递增序列

[复制链接]
发表于 2017-7-28 17:08:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
已知$n$个有限整数集,标号为$s_1, ..., s_n$,分别从$s_1,...,s_n$中各选取1个数字,组成序列$a_1,...,a_n$,要使得$a_1,...,a_n$拥有最长的递增子序列(这里的子列要求相邻,即$a_1,...,a_n$中存在子列$a_{n_0} < a_{n_0+1} < ... < a_{n_0+k}$且$k$最大)。

求编程实现思路~


背景
“2012年01月”假设是个实体,然后我说“2012年1月”,也要匹配上“2012年01月”

为了效率,我就把“2012年1月”逐字匹配,得到的结果是:第一个数字2,匹配了“2012年01月”的第1、4个位置,第二个数字0,匹配了第2个位置,以此类推,我得到
[1,4]
[2]
[3,7]

理论上所有序列都有可能,我要找出最大的递增的序列,来看它与“2012年01月”有多匹配。这个例子应该要找到[1,2,3,4,5,7,8]。

要考虑递增,是因为一般情况下来说,文本允许增删,也允许错别字,但不允许乱序。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-1-22 06:22 , Processed in 0.046970 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表