数据结构与算法之美
王争
前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 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?

王争 2018-12-26
淘宝的“双十一”购物节有各种促销活动,比如“满 200 元减 50 元”。假设你女朋友的购物车中有 n 个(n>100)想买的商品,她希望从里面选几个,在凑够满减条件的前提下,让选出来的商品价格总和最大程度地接近满减条件(200 元),这样就可以极大限度地“薅羊毛”。作为程序员的你,能不能编个代码来帮她搞定呢?
要想高效地解决这个问题,就要用到我们今天讲的动态规划(Dynamic Programming)。

动态规划学习路线

动态规划比较适合用来求解最优问题,比如求最大值、最小值等等。它可以非常显著地降低时间复杂度,提高代码的执行效率。不过,它也是出了名的难学。它的主要学习难点跟递归类似,那就是,求解问题的过程不太符合人类常规的思维方式。对于新手来说,要想入门确实不容易。不过,等你掌握了之后,你会发现,实际上并没有想象中那么难。
为了让你更容易理解动态规划,我分了三节给你讲解。这三节分别是,初识动态规划、动态规划理论、动态规划实战。
第一节,我会通过两个非常经典的动态规划问题模型,向你展示我们为什么需要动态规划,以及动态规划解题方法是如何演化出来的。实际上,你只要掌握了这两个例子的解决思路,对于其他很多动态规划问题,你都可以套用类似的思路来解决。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(148)

  • zixuan
    贪心:一条路走到黑,就一次机会,只能哪边看着顺眼走哪边
    回溯:一条路走到黑,无数次重来的机会,还怕我走不出来 (Snapshot View)
    动态规划:拥有上帝视角,手握无数平行宇宙的历史存档, 同时发展出无数个未来 (Versioned Archive View)
    2018-12-30
    3
    273
  • 🌀🐑hfy🐣
    首先得有个女朋友
    2018-12-26
    3
    55
  • 茴香根
    我理解的动态规划,就是从全遍历的递归树为出发点,广度优先遍历,在遍历完每一层之后对每层结果进行合并(结果相同的)或舍弃(已经超出限制条件的),确保下一层遍历的数量不会超过限定条件数完W,通过这个操作达到大大减少不必要遍历的目的。
    在空间复杂度优化上,通过在计算中只保留最优结果的目的重复利用内存空间。
    2018-12-26
    49
  • 郭霖
    王争老师动态规划讲得确实精彩,就是课后练习没有答案,有时候解不出来会很难受。我是看了下一篇文章的讲解然后明白了这篇文章的课后习题解法,这里分享一下吧,希望对大家有帮助。

    int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};

    public int yanghuiTriangle(int[][] matrix) {
        int[][] state = new int[matrix.length][matrix.length];
        state[0][0] = matrix[0][0];
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (j == 0) state[i][j] = state[i - 1][j] + matrix[i][j];
                else if (j == matrix[i].length - 1) state[i][j] = state[i - 1][j - 1] + matrix[i][j];
                else {
                    int top1 = state[i - 1][j - 1];
                    int top2 = state[i - 1][j];
                    state[i][j] = Math.min(top1, top2) + matrix[i][j];
                }
            }
        }
        int minDis = Integer.MAX_VALUE;
        for (int i = 0; i < matrix[matrix.length - 1].length; i++) {
            int distance = state[matrix.length - 1][i];
            if (distance < minDis) minDis = distance;
        }
        return minDis;
    }
    2019-01-02
    5
    42
  • P@tricK
    老师你这个只能精确到元,女朋友羊毛精说要求精确到0.01元,时间空间复杂度增大100倍🐶

    作者回复: 👍 说的没错

    2018-12-26
    1
    18
  • 煦暖
    老师你好,您在专栏里提到好几次哨兵,啥时候给我们讲解一下呢?
    2018-12-28
    1
    13
  • Monday
    1、这里我特别强调一下代码中的第 6 行,j 需要从大到小来处理。
    这里自己写代码调试完才恍然大悟,第i轮循环中新设置的值会干扰到后面的设值。

    2、特别感谢争哥今天让其他的课程的老师来客串了一节课,让我有了更多的时间学习本节。

    作者回复: 不着急你慢慢学就是了 不用非得跟的那么紧

    2018-12-28
    1
    11
  • 失火的夏天
    杨辉三角的动态规划转移方程是:S[i][j] = min(S[i-1][j],S[i-1][j-1]) + a[i][j]。
    其中a表示到这个点的value值,S表示到a[i][j]这个点的最短路径值。
    这里没有做边界条件限制,只是列出一个方程通式。边界条件需要在代码里具体处理。个人感觉动态规划的思想关键在于如何列出动态规划方程,有了方程,代码基本就是水到渠成了。
    2018-12-27
    7
  • G.S.K
    关于knapsack2函数
    1 states表示当前背包总重量所有可能取值的集合
    2 如果将第i个物品放入背包,我们需要在当前背包总重量的所有取值中,找到小于等于j的(j=w-items[i])
    3 为什么第6行j需要从大到小来处理?因为循环的目的是在当前背包总重量的所有可能取值中,找到小于等于j的,如果j从小到大来处理,states[j+items[i]] = true;这个赋值会影响后续的处理
    public static int knapsack2(int[] items, int n, int w) {
      boolean[] states = new boolean[w+1]; // 默认值 false
      states[0] = true; // 第一行的数据要特殊处理,可以利用哨兵优化
      states[items[0]] = true;
      for (int i = 1; i < n; ++i) { // 动态规划
        for (int j = w-items[i]; j >= 0; --j) {// 把第 i 个物品放入背包
          if (states[j]==true) states[j+items[i]] = true;
        }
      }
      for (int i = w; i >= 0; --i) { // 输出结果
        if (states[i] == true) return i;
      }
      return 0;
    }
    2019-03-04
    1
    6
  • feifei
    这个动态规划学习了三天了,把老师的代码都手练了一遍,感觉对动态规划有点感觉了!然后在写这个课后题,我也练了一遍,我练了这么多,但我觉得动态规则这个最重要的是每层可达的状态这个怎么计算的,这是重点,我开始的时候,用纸和笔,把老师的第一例子,中的状态都画了出来,然后再来看代码,感觉很有帮助!

    杨晖三角的代码我我也贴出来,希望对其他童鞋有帮助,老师,也麻烦你帮忙看下,看我的实现是否存在问题,谢谢!

    由于这个限制,限制长度,没有贴出来倒推出路径,可查看我的git
    https://github.com/kkzfl22/datastruct/blob/master/src/main/java/com/liujun/datastruct/algorithm/dynamicProgramming/triangle/Triangle.java


    int[][] status = new int[triangles.length][triangles[triangles.length - 1].length];

        int startPoint = triangles.length - 1;
        int maxpoint = triangles[triangles.length - 1].length;

        // 初始化相关的数据
        for (int i = 0; i <= startPoint; i++) {
          for (int j = 0; j < maxpoint; j++) {
            status[i][j] = -1;
          }
        }

        // 初始化杨晖三解的第一个顶点
        status[0][startPoint] = triangles[0][startPoint];

        // 开始求解第二个三角形顶点
        // 按层级遍历
        for (int i = 1; i <= startPoint; i++) {
          // 加入当前的位置节点
          int currIndex = 0;
          while (currIndex < maxpoint) {
            if (status[i - 1][currIndex] > 0) {
              // 计算左节点
              int leftValue = status[i - 1][currIndex] + triangles[i][currIndex - 1];

              // 1,检查当前左节点是否已经设置,如果没有,则直接设置
              if (status[i][currIndex - 1] == -1) {
                status[i][currIndex - 1] = leftValue;
              } else {
                if (leftValue < status[i][currIndex - 1]) {
                  status[i][currIndex - 1] = leftValue;
                }
              }
              // 计算右节点
              int rightValue = status[i - 1][currIndex] + triangles[i][currIndex + 1];

              if (status[i][currIndex + 1] == -1) {
                status[i][currIndex + 1] = rightValue;
              }
              currIndex++;
            }
            currIndex++;
          }
        }

        int minValue = Integer.MAX_VALUE;
        for (int i = 0; i < maxpoint; i++) {
          if (minValue > status[startPoint][i] && status[startPoint][i] != -1) {
            minValue = status[startPoint][i];
          }
        }
        System.out.println("最短路径结果为:" + minValue);

    2018-12-28
    6
  • Andylee
    老师,倒数第二段的代码(背包升级版)的12行的if条件判断是不是写错了

    作者回复: 是的 我改下

    2018-12-26
    6
  • 德尼
    解答开篇代码的19行那的判断为什么是 j==-1?在上面的循环中假设从 w 到 3*w+1 没有可解的话,那么 j 的结果不应该是 3*w+2 吗?
    2019-01-30
    4
  • 不上进的码农
    关于课后杨辉三角最短路径的问题,应该用动态规划的两种方式都可以实现。1,状态转移,和背包问题升级版类似,同样使用二维数组记录,一维表示行,二维表示列,值保存最短路径,两种途径到达同一节点,我们只保存路径最短的值,然后一行一行遍历完,最后把最后一行进行排序,选择最小的即可。需要注意的是,在生成二维数组的时候最好是每行遍历生成,如第一行只有一个,第二行两个,这样可以节省一半的空间。2,方程转移,也就是从下往上来,每一个节点只有上层的两个节点能到达,也就是(i,j)节点,要么途径(i-1,j-1)节点,要么途径(i-1,j)节点,那么选择二者的最小值加上当前节点的数字,就是当前节点的最小值了,最后把最后一行排序选最小就OK了
    2019-01-05
    4
  • 任悦
    思考题这个杨辉三角有点巧了,最短路径就是最左边一列
    2018-12-28
    4
  • 黄均鹏
    解开这道题的前提是首先得先有个女朋友

    作者回复: 男朋友也可以的:)

    2019-02-25
    3
  • 像玉一样的石头
    老师,请教个问题,想了好久不知道该如何求解
    关于汇率方面的,比如手里有100人民币,设计一个汇率转换的环,比如人民币-》美元-》日元-》韩元-》人民币,兑换一圈后,手里的钱一直在增加,这个问题该如何求解呢
    2018-12-27
    3
  • mαnajay
    记录一下自己的 swift 版本一维数组动态规划装东西
    /*
     *
     * 动态规划
     
     * 注意 Source 里面应该是 public, 运行时才不好报错
     **/
    public struct DynamicProgramming {
        init() {
        }
        
        public static func knapsack2(_ items: Array<Int>, _ maxWeight: Int ) -> Void {
            let count = items.count
            var states = Array<Bool>.init(repeating: false, count: count + 1)
            // 首个没有放入
            states[0] = true
            // 首个放入了
            states[items[0]] = true
            for i in 1..<count { // 动态规划
                // 从去除已经计算过重量的最大的重量开始算起i, 把第 i 个物品放入背包
                for j in 0 ... (maxWeight - items[i]) {// 除了第 i 个物品, 剩余重量,如果有计算过的, 那么再加上第 i 个物品, 记录此时总重量的状态
                    if (states[j] == true) {
                        let total = j + items[i]
                        states[total] = true
                    }
                }
            }
            for v in (0 ... maxWeight).reversed() {
                if states[v] {
                    print("maxWeight index: \(v)")
                    break
                }
            }
        }
    }
    2019-04-19
    2
  • 春去春又来
    老师,这是我基于理解动态规划之后写出的优化版斐波那契数列,是否算是动态规划入门了 - -
    function faibonacci(n) {
        //可以基于动态规划的思想去优化
        //存储每一个步骤的值,然后推导出之后的值
        let hash = {};
        const calcu = (n) => {
            if (n === 1 || n === 2) return 1;
            let a = hash[n - 1] || calcu(n - 1);
            let b = hash[n - 2] || calcu(n - 2);
            return a + b;
        }
        for (let i = 1; i <= n; i++) {
            hash[i] = calcu(i)
        }
        return hash[n]
    }

    作者回复: 👍 你还得把我文章里涉及的所有题目都搞明白、会默写才算入门呢

    2019-02-15
    2
  • Monday
    思考题,杨辉三角,思路(Java版):
    记入参的数据结构是List<List<Integer>> list
    状态转移方程为f(i,j)=list.get(i).get(j)+min(list.get(i - 1).get(j - 1)),list.get(i-1).get(j))
    注意:需要注意数组越界问题。
    2019-01-09
    2
  • @
    第三部分的代码,第11行是不是有问题?根据代码推不出states[4][3]=true???
    2018-12-26
    2
收起评论
99+
返回
顶部