282842712474 发表于 2017-7-28 17:08:38

动态规划与最大递增序列

已知$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个位置,以此类推,我得到




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

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

页: [1]
查看完整版本: 动态规划与最大递增序列