数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?

王争 2019-01-02
Trie 树那节我们讲过,利用 Trie 树,可以实现搜索引擎的关键词提示功能,这样可以节省用户输入搜索关键词的时间。实际上,搜索引擎在用户体验方面的优化还有很多,比如你可能经常会用的拼写纠错功能。
当你在搜索框中,一不小心输错单词时,搜索引擎会非常智能地检测出你的拼写错误,并且用对应的正确单词来进行搜索。作为一名软件开发工程师,你是否想过,这个功能是怎么实现的呢?

如何量化两个字符串的相似度?

计算机只认识数字,所以要解答开篇的问题,我们就要先来看,如何量化两个字符串之间的相似程度呢?有一个非常著名的量化方法,那就是编辑距离(Edit Distance)。
顾名思义,编辑距离指的就是,将一个字符串转化成另一个字符串,需要的最少编辑操作次数(比如增加一个字符、删除一个字符、替换一个字符)。编辑距离越大,说明两个字符串的相似程度越小;相反,编辑距离就越小,说明两个字符串的相似程度越大。对于两个完全相同的字符串来说,编辑距离就是 0。
根据所包含的编辑操作种类的不同,编辑距离有多种不同的计算方式,比较著名的有莱文斯坦距离(Levenshtein distance)和最长公共子串长度(Longest common substring length)。其中,莱文斯坦距离允许增加、删除、替换字符这三个编辑操作,最长公共子串长度只允许增加、删除字符这两个编辑操作。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(106)

  • ext4
    Trie树和编辑距离,很多年前我去Google面试的时候都被考过。还记得Trie树是问我怎么存储美国的10位电话号码,可以最快速查找一个号码是否是空号,我答上来了;不过关于编辑距离我当时没想出来用dp。
    2019-01-02
    62
  • zixuan
    补充一下,中文纠错很多时候是通过拼音进行的,比如 "刘得花"->"liudehua"->"刘德华". 拼音检索方法也有很多,比如可以把热门词汇的拼音字母组织成Trie树,每个热词的结尾汉字的最后一个拼音字母就是叶子,整体性能就是O(n)的,n为query的拼音总长度. 除了拼音外也有根据字形(二维文字版的编辑距离?)甚至语义等做的纠错策略。
    传统搜索引擎中的查询词智能提示、纠错、同义词、近义词、同好词、相关搜索、知识图谱等系列功能统称为用户的意图识别模块。

    作者回复: 👍好厉害

    2019-01-03
    42
  • 王超
    老师,能帮忙解释下这个公式吗,有一点费解, a[i]==b[j] 时,为什么是:
    min(min_edist(i-1,j)+1, min_edist(i,j-1)+1,min_edist(i-1,j-1)) 而不是
    min(min_edist(i-1,j), min_edist(i,j-1),min_edist(i-1,j-1))
    为什么要 + 1 啊
    2019-01-25
    9
    19
  • blacknhole
    有个疑问:
    以下内容涉及“如何编程计算莱文斯坦距离?”一节。

    (1)文中对递归树中的状态三元组(i, j, edist)的解释是,“状态包含三个变量 (i, j, edist),其中,edist表示处理到 a[i] 和 b[j] 时,已经执行的编辑操作的次数。”这里的“处理到a[i]和b[j]时”,其实是在说将要处理但还并未处理a[i]和b[j]。edist并不包括对a[i]和[j]的编辑操作。递归树图片后紧接着的图片中,(i, j, min_edist)的min_edist也并不包括对a[i]和[j]的编辑操作。

    (2)而二维状态表图片中每格的值和动态规划的实现代码中minDist[i][j]两者均代表:到处理完a[i]和b[j]之后为止,已经执行的编辑操作的最少次数。根据这个意思,可知状态转移方程中的min_edist(i, j)也是包括对a[i]和[j]的编辑操作的。如果按照(1)中的意思,状态转移方程中的min_edist(i, j)就不应该包括对a[i]和[j]的编辑操作,也不应该判断a[i]和b[j]是否相等,而应该判断的是a[i - 1]和b[j - 1]是否相等;并且动态规划的实现代码中循环终止条件就不应是小于n或m,而应是小于等于n或m。

    为什么会有(1)与(2)这样的在文章前后表达上的不一致?

    作者回复: 👍你说的没错 不仅这一节 前面两节课都是这样。递归树是根据回溯算法代码实现写的。但是动规代码用你讲到的另一种思路理解更容易。我当时写的时候 也想能不能统一。最后发现不好统一。你可以分割开来看 或者 把它们当作两种状态表示方法来看 不影响理解

    2019-01-02
    3
    17
  • G.S.K
    动态规划问题的思路总结:第一步:如果待解决的问题为func(n),自己可以假设func(n-1)、func(n-2)……func(1)都已经解出,然后就是如何利用这些结果来推导出func(n),经过这么分析就可以得出推导方程。第二步:设计dp数组来保存func(n)(一维数组、二维数组等)。第三步:从0开始遍历,按照状态转移方程计算出func(n)保存到dp数组
    举例,以下这些leetcode动态规划相关的题都可以直接套用这个解题思路

    一维dp数组的题目
    322. Coin Change
    121. Best Time to Buy and Sell Stock
    53. Maximum Subarray
    300. Longest Increasing Subsequence
    152. Maximum Product Subarray

    二维dp数组的题目
    152. Maximum Product Subarray
    120. Triangle
    2019-03-22
    1
    13
  • Jack_Cui
    老师 最长公共子串要求的是连续的 对于编辑距离应该是最长公关子序列吧
    2019-01-17
    13
  • Sharry
    思考题的解法还是很精妙的
    递推公式:
    a[0...i] 的最长子序列为: a[i] 之前所有比它小的元素中子序列长度最大的 + 1

    代码实现:
    ```
    #include<iostream>

    using namespace std;

    // 动态规划求 a 的最上升长子序列长度
    #include<iostream>

    using namespace std;

    // 动态规划求 a 的最上升长子序列长度
    int longestSubsequence(int *a, int n) {
    // 创建一个数组, 索引 i 对应考察元素的下标, 存储 arr[0...i] 的最长上升子序列大小
    int *lss_lengths = new int[n];
    // 第一个元素哨兵处理
    lss_lengths[0] = 1;
    // 动态规划求解最长子序列
    int i, j, max;
    for (i = 1; i < n; i++) {
    // 计算 arr[0...i] 的最长上升子序列
    // 递推公式: lss_lengths[i] = max(condition: j < i && a[j] < a[i] value: lss_lengths[j] + 1)
    max = 1;
    for (j = 0; j < i; j++) {
    if (a[i] > a[j] && lss_lengths[j] >= max) {
    max = lss_lengths[j] + 1;
    }
    }
    lss_lengths[i] = max;
    }
    int lss_length = lss_lengths[n - 1];
    delete[]lss_lengths;
    return lss_length;
    }

    void main() {
    const int n = 7;
    int arr[n] = { 2, 9, 3, 6, 5, 1, 7 };;
    cout << longestSubsequence(arr, n) << endl;
    getchar();
    }
    2019-01-03
    1
    11
  • G.S.K
    第二遍学习,看留言有同学不理解状态转移表的填充过程,现总结一下状态转移表的填充详细过程和对应的字符编辑操作,望老师指正:
    1 minDist[i][j]表示处理完a[i]和b[j]时(a[0...i]已全部转换到b[0...j]),需要的最小编辑次数
    2 a[i]和b[j]不相等时,状态转移公式为:minDist[i][j]=min(minDist(i-1,j)+1, minDist(i,j-1)+1,minDist(i-1,j-1))
       1) 如果minDist[i][j]=minDist(i-1,j)+1,现分析一下这个状态转移的具体过程。minDist(i-1,j)表示a[0...i-1]已全部转换到b[0...j],如何编辑字符才能从minDist(i-1,j)到达minDist[i][j]这个状态呢?要么将a[i]这个字符删除,要么在b[j]后边添加一个跟a[i]相同的字符(这里编辑的操作跟老师讲的回溯法的操作是不一样的)
       2)如果minDist[i][j]=minDist(i-1,j-1),现分析一下这个状态转移的具体过程。如何编辑字符才能从minDist(i-1,j-1)到达minDist[i][j]这个状态呢??将a[i]替换为b[j]或者将b[j]替换为a[i]即可
      3) 如果minDist[i][j]=minDist(i,j-1)+1,跟上边第一种情况类似
    3 a[i]和b[j]相等时比较简单,不需要做字符的编辑
    2019-03-24
    3
    10
  • 郭霖
    思考题java版解答:
    public int longestIncreaseSubArrayDP(int[] array) {
        if (array.length < 2) return array.length;
        int[] state = new int[array.length];
        state[0] = 1;
        for (int i = 1; i < state.length; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (array[j] < array[i]) {
                    if (state[j] > max) max = state[j];
                }
            }
            state[i] = max + 1;
        }
        int result = 0;
        for (int i = 0; i < state.length; i++) {
            if (state[i] > result) result = state[i];
        }
        return result;
    }
    2019-01-08
    2
    9
  • 沉睡的木木夕
    那个状态转移表是怎么填充的?我来回看了几遍还是不知道里面的值怎么来的,感觉跟前面分析的扯不上任何关系
    2019-01-22
    1
    7
  • 王者归来
    老师,第一行初始化值,如何理解?
    if (a[0] == b[j]) minDist[0][j] = j;
    else if (j != 0) minDist[0][j] = minDist[0][j-1]+1;
    else minDist[0][j] = 1;
    2019-01-31
    1
    6
  • G.S.K
    莱温斯坦距离状态表,初始化第0行和第0列代码逻辑有点复杂,可以简化一下,修改状态表为如下形式
    ∅ m t a c n u
    ∅ 0 1 2 3 4 5 6
    m 1 0 1 2 3 4 5
    i 2 1
    t 3 2
    c 4 3
    m 5 4
    u 6 5
    代码就可以简化了
    int[][] minDist = new int[n+1][m+1]
      for (int j = 0; j <= m; ++j) { 初始化第0行
        minDist[0][j] = j;
      }
      for (int i = 0; i <= n; ++i) { 初始化第0列
        minDist[i][0] = i;
      }
    最终return minDist[n][m];
    2019-03-24
    3
    5
  • Kudo
    思考题解答:
    状态转移公式:maxLen[i] = max(maxLen[j]+(1 if j<i else 0)) for any j < i
    python代码:
    def maxOrderedSeq(seq):
        maxLen = [1] * len(seq) # 初始化为1
        
        for i in range(1, len(seq)): # i从1开始
            for j in range(i-1,-1,-1): # j从i-1到0
                if seq[j] <= seq[i]:
                    maxLen[i] = maxLen[j] + 1
                    break # 满足则退出
            if maxLen[i] == 1: # 比前面所有元素小
                maxLen[i] = maxLen[i-1]
                
        print(maxLen)
                
    # usage
    seq = [2, 9, 3, 6, 5, 1, 7]
    maxOrderedSeq(seq)
    2019-01-03
    1
    5
  • saber
    老师我有个疑问(急),希望老师能够帮忙回答下,这也是大部分留言中没能解决的疑问。
    在莱文斯坦距离讲解时,那里的状态方程是怎么直接写出来的?这一点是我最不能理解的,当然在问该问题之前,我已经尽我所能的尝试理解老师的文章,并且把留言也都翻了一遍。老师请看我下面的陈述:

    一:按照老师文章的讲解顺序,先分析了如何用回溯方法,然后绘制了递归树,从递归树中又分析出了具有重复的子结构,接着又画出了状态简图(递归树下面的图,不知道怎么表达),从这幅简图中清晰的看出来状态的转移方式,接下来重点来了!!!文章接着就写出来状态转移方程(不理解的地方)!我在留言中发现,老师对这点的解释是说「状态转移方程与递归树无关,递归树仅仅表达了问题具有重复子结构」,如果按照老师的说法,不根据递归树分析出状态转移过程,那该怎么直接写出状态转移方程(要能够合理的推断出来,而不是靠经验,否则还是无法掌握动态规划)?目前来看,我在文章中没有发现具有这样的逻辑推断。我之前的理解是说,我们其实可以在递归树中分析出状态转移方程如何写,然后这样就形成了一个闭环,由回溯->递归树->状态转移方程。希望在这里老师能够给出一个合理的解释?

    二:抛开上面的一些问题,咱们单独看莱问斯坦距离状态转移公式,先假设,按照递归树和递归树下面的图可以知道状态转移的过程(这是一个前提假设)。在留言中的第 4 条「blacknhole」这位同学的留言中,我也有相同的疑问,(i , j, min_edist) 到底表达的是什么状态?(处理完 a[i] b[j] 后的最小距离? or 刚要处理 a[i] b[j] 时对应的最小距离?),

    接下来按照二种不同的表达来看看状态方程如何推断出来:

    1、 如果表达的含义是 「处理完 a[i] b[j] 后的最小距离」

    那么其实从回溯算法中可以知道(因为 i j 的前一个状态已经处理完了,比如 min_edist(i-1,j) 就代表了前一个状态。)

    if (a[i] != b[j])

    ​ min_edist(i, j) =1+ min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1))

    if (a[i] == b[j] )

    ​ min_edist(i, j) = min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1))

    2、如果表达的含义是「刚要处理 a[i] b[j] 时对应的最小距离」

    那么我们可以这么想,当前 i,j min_edist 表示还没有处理过 i,j 时对应的状态,因此我们需要考虑之前的状态是怎么传递到这里来的

    min_edist(i, j) =

    min(min_edist(i-1,j)+1, min_edist(i, j-1)+1, min_edist(i-1, j-1) + (a[i-1] == b[j-1]? 0 : 1))



    从上面的两种推断发现,我觉的都是比较合理的,但是没有一种的结果与老师给的状态转移方程是一致的(这一点比较疑惑)?所以对于老师的状态转移方程肯定不是从递归树中直接推导出来的,那么请问老师这个状态转移方程该怎么合理的推断出来(我觉得这个问题不是靠多做题解决的,必须要知道推理逻辑才能彻底掌握动态规划)?



    三:接下来还有一个问题(前提假设是老师的状态方程是正确的,具体逻辑还不能理解)

    那么如果根据状态状态方程,来填充状态表的第 0 行 第 0列呢(留言中也有许多这方面的疑问)?按照我的理解,既然状态转移方程我们知道了,那么其实从状态转移方程中就可以直接填充表格了,比如填充第 0 行时,因为从状态转移方程中我们发现有 i - 1,j-1 因此当计算第 0 行时,带有 i-1 项的就可以省略了,因此状态转移方程就剩下 (i, j-1) 项了。然后其实就不用分 a[i] b[j] 是否相等了,但是回头看老师的代码,却不明白为什么还要分 a[i] b[j] 相等不相等。希望老师能够解释一下!



    综上:如果老师觉得我描述的问题不清楚,那么希望老师看看这篇文章的其他问题留言,总结一下大家到底哪里不理解,并且对不理解的地方从新更新下当前文章,具体解释一下,比如老师在留言中说过「不能从递归树中直接推导出状态转移方程,两者没有联系」,那么希望老师在文章的对应地方直接表明这句话,并且在加上额外的说明,比如如何推断出状态转移方程,这样整篇文章才能让更多的人从本质上理解动态规划!



    最后希望老师能够认真给出我上面几个问题的解答,谢谢老师!

    作者回复: 你这个问题太多了 我写篇文章给你 你关注:小争哥

    2019-09-24
    1
    4
  • 传说中的成大大
    if (a[i] == b[j]) minDist[i][j] = min(
    minDist[i-1][j]+1,minDist[i][j-1]+1,minDist[i-1][j-1])不明白的是为什么minDist[i-1][j]或者mindist[i][j-1] 要+1呢?

    作者回复: (i-1,j)这个状态转移到(i, j)这个状态,minDist要加一
    (i, j)同上
    (i-1, j-1)这个状态转移到(i, j)这个状态,minDist保持不变,因为a[i]==b[j]

    2019-02-28
    5
    4
  • Kudo
    选这个专栏的初衷就是为了学习动态规划,作者对这部分内容的讲解我还是比较满意的。两个月前,闲来无事刷了几天LeetCode,遇到一道字符串模式匹配的题,不是结果错误就是复杂度不达标,怎么也搞不定。看了论坛里给出的高赞解答,清一色采用了动态规划的解题方法,当时没有算法基础,真的是看不懂啊,遂放弃。现在经过几节课的学习理出一些思路来,收获颇丰,理论看得比较明白了,程序照着文中的例子也能写个大概,但感觉掌握得还是不牢靠,还需要多加练习。谢谢作者!
    2019-01-02
    4
  • 俊杰
    为什么到后面留言这么少?

    在编辑距离里面, 状态转移方程,第二种case ,是不是可以改为:

    如果:a[i]==b[j],那么:min_edist(i, j) 就等于:min_edist(i-1,j-1)

    a[i]==b[j]
    a[0..i] 和 b[0..j] 的编辑距离就等价于 a[0..i-1] 和 b[0..j-1]的编辑距离
        
    2019-01-31
    3
  • Ricky
    老师,您好,您这节内容讲的很清晰透彻,我以前做动态规划问题是直接寻找状态转移方程,基本只能处理一些简单的动态规划问题,没有形成系统的解题思路,听了您这一节后,我觉得将回溯简单思路逐步转化为动规思路让我受益匪浅,但是当我试着将这套思路应用于求解最长递增子序列时却感觉回溯更麻烦,不知能否指点一二

    作者回复: 我的讲解并不是为了指导做题。所以,我讲解的时候,从为什么要动态规划讲起,所以废话比较多。实际上,你理解理论之后,解动态规划题目的时候,一般可以直接写最优子结构,也就是状态转移方程,不需要再从回溯解法开始。。。

    2019-01-04
    3
  • 菜菜
    老师,为什么当a[i]==b[j]时,minDist[i][j]不能直接等于minDist[i-1][j-1],而要等于min(minDist[i-1][j]+1,minDist[i][j-1]+1,minDist[i-1][j-1])
    2019-03-05
    2
  • feifei
    要自己思考这个问题,感觉真不容易,因为思路错误,走了不少弯路,花了5天的休息时间,终于解出来了,写出来了,感觉是容易了,但这个思考的过程,感觉自己收获不少,尝试了很多种的解法,然后都一一的否决!


    这是我写的递归求解,

    public int recursionCount4(int[] arrays, int index) {

        if (index == 0) {
          return 1;
        }
        int max = 0;
        //此问题的解,递归的核心就是在之前的序列中找到最大递增子序列加1
        //所以需要遍历此此之前的全部数据项
        for (int i = 0; i < index; i++) {
          //递归求解每项的最递增序列
          int value = recursionCount4(arrays, i);
          if (arrays[i] < arrays[index]) {
            if (value > max) {
              max = value;
            }
          }
        }

        return max + 1;
      }



    public void countDynamic(int[] arrays) {
        int length = arrays.length;

        int[] status = new int[length];

        status[0] = 1;

        int commMax = 0;

        for (int i = 1; i < length; i++) {
          int max = 0;
          for (int j = 0; j < i; j++) {
            if (arrays[j] < arrays[i]) {
              if (status[j] > max) {
                max = status[j];
              }
            }
          }
          status[i] = max + 1;

          if (status[i] > commMax) {
            commMax = status[i];
          }
        }

        System.out.println("最大递增序列为 :" + commMax);
        int maxComp = commMax;
        System.out.println("递增:" + Arrays.toString(status));

        for (int i = length - 1; i >= 0; i--) {
          if (status[i] == maxComp) {
            System.out.print("-->" + arrays[i]);
            maxComp = maxComp - 1;
          }
        }
      }


    2019-01-11
    2
收起评论
99+
返回
顶部