数据结构与算法之美
王争
前Google工程师
立即订阅
71408 人已学习
课程目录
已完结 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 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

王争 2018-12-31
上一节,我通过两个非常经典的问题,向你展示了用动态规划解决问题的过程。现在你对动态规划应该有了一个初步的认识。
今天,我主要讲动态规划的一些理论知识。学完这节内容,可以帮你解决这样几个问题:什么样的问题可以用动态规划解决?解决动态规划问题的一般思考过程是什么样的?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系?
理论的东西都比较抽象,不过你不用担心,我会结合具体的例子来讲解,争取让你这次就能真正理解这些知识点,也为后面的应用和实战做好准备。

“一个模型三个特征”理论讲解

什么样的问题适合用动态规划来解决呢?换句话说,动态规划能解决的问题有什么规律可循呢?实际上,动态规划作为一个非常成熟的算法思想,很多人对此已经做了非常全面的总结。我把这部分理论总结为“一个模型三个特征”。
首先,我们来看,什么是“一个模型”?它指的是动态规划适合解决的问题的模型。我把这个模型定义为“多阶段决策最优解模型”。下面我具体来给你讲讲。
我们一般是用动态规划来解决最优问题。而解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(73)

  • yaya
    可以看做爬阶梯问题,分别可以走1.3.5步,怎么最少走到9步,动态转移方程为f(9)=1+min(f(8),f(6),f(4))

    作者回复: 👍

    2019-01-03
    1
    104
  • 郭霖
    动态规划状态转移表解法:

    public int minCoins(int money) {
      if (money == 1 || money == 3 || money == 5) return 1;
      boolean [][] state = new boolean[money][money + 1];
      if (money >= 1) state[0][1] = true;
      if (money >= 3) state[0][3] = true;
      if (money >= 5) state[0][5] = true;
      for (int i = 1; i < money; i++) {
        for (int j = 1; j <= money; j++) {
          if (state[i - 1][j]) {
            if (j + 1 <= money) state[i][j + 1] = true;
            if (j + 3 <= money) state[i][j + 3] = true;
            if (j + 5 <= money) state[i][j + 5] = true;
            if (state[i][money]) return i + 1;
          }
        }
      }
      return money;
    }
    2019-01-03
    2
    34
  • Alpha.
    回溯算法实现矩阵最短路径会有边界问题,下面是修改后的代码。
    private static int MIN_DIS = Integer.MAX_VALUE;
    public static void minDisByBT(int i, int j, int[][] w, int n, int distance) {
            distance += w[i][j];
            if (i == n - 1 && j == n - 1) {
                if (distance < MIN_DIS) MIN_DIS = distance;
                return;
            }
            if (i < n - 1) {
                minDisByBT(i + 1, j, w, n, distance);
            }
            if (j < n - 1) {
                minDisByBT(i, j + 1, w, n, distance);
            }
        }
    2019-02-22
    12
  • 煦暖
    状态转移表法,二维状态表的图中,第一行下面的表达式:
    文中“min(4+3, 8+3)”应该是“min(4+3, 9+3)”

    作者回复: 嗯嗯 是的 笔误 抱歉

    2019-01-03
    11
  • feifei
    经过一个星期的努力,这个动态规划终于有点感觉了,今天来做题,我也来试试解这个题目,在看了第一个童鞋的解法后,感觉这个写的太死了,再就是没有反推出哪些币的组合,我就自己来实现了下!
    我也想说动态规划的解,真不容易啊,我按照老师提供的方法,先使用回塑写出了暴力搜索,然后再画出了递归树,找到状态组合,然后才来写这个动态规划,感觉好复杂,不过吧,这个使用状态转移方程,我感觉更难,比这个递归还难写。。。。。。,最主要是这个状态想不到,但这个动态规划代码写完了,我又感觉能写方程了,我想哭。。。。。。。


    public int countMoneyMin(int[] moneyItems, int resultMemory) {

        if (null == moneyItems || moneyItems.length < 1) {
          return -1;
        }

        if (resultMemory < 1) {
          return -1;
        }

        // 计算遍历的层数,此按最小金额来支付即为最大层数
        int levelNum = resultMemory / moneyItems[0];
        int leng = moneyItems.length;

        int[][] status = new int[levelNum][resultMemory + 1];

        // 初始化状态数组
        for (int i = 0; i < levelNum; i++) {
          for (int j = 0; j < resultMemory + 1; j++) {
            status[i][j] = -1;
          }
        }

        // 将第一层的数数据填充
        for (int i = 0; i < leng; i++) {
          status[0][moneyItems[i]] = moneyItems[i];
        }

        int minNum = -1;

        // 计算推导状态
        for (int i = 1; i < levelNum; i++) {
          // 推导出当前状态
          for (int j = 0; j < resultMemory; j++) {
            if (status[i - 1][j] != -1) {
              // 遍历元素,进行累加
              for (int k = 0; k < leng; k++) {
                if (j + moneyItems[k] <= resultMemory) {
                  status[i][j + moneyItems[k]] = moneyItems[k];
                }
              }
            }

            // 找到最小的张数
            if (status[i][resultMemory] >= 0) {
              minNum = i + 1;
              break;
            }
          }

          if (minNum > 0) {
            break;
          }
        }

        int befValue = resultMemory;

        // 进行反推出,币的组合
        for (int i = minNum - 1; i >= 0; i--) {
          for (int j = resultMemory; j >= 0; j--) {
            if (j == befValue) {
              System.out.println("当前的为:" + status[i][j]);
              befValue = befValue - status[i][j];
              break;
            }
          }
        }

        return minNum;
      }

    作者回复: 👍 都有这个似懂非懂的过程的 多练习 慢慢就有感觉了

    2019-01-06
    10
  • 攻玉

    # 1. 回溯 : 太慢了
    coin = 0
    def minCoin(money):
        global coin
        if money == 1: return 1
        if money == 2: return 2
        if money == 3: return 1
        if money == 4: return 2
        if money == 5: return 1
    # if money <= 0: return

        coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))
        print(money , coin)
        return coin

    print(minCoin(10))


    # 2.写备忘录, 记录重复的递归项:
    # 速度提升不知道几十万倍 ! 缺点就是有递归层数的限制 , 超过最大递归层数(几百?)会报错
    import numpy as np
    map = {} # 初始化一个 dict
    coin = 0
    def minCoin(money):
        global coin
        # 先查表 :
        if money in map: # 如果在 map 的第一列里面 , 说明记录过.
            return map[money] # 直接返回 minCoin
        if money == 1: return 1
        if money == 2: return 2
        if money == 3: return 1
        if money == 4: return 2
        if money == 5: return 1
    # if money <= 0: return

        coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))
        map[money] = coin # 放入map

        return coin
        
    print(minCoin(100))
    print(map)


    '''

    # 3.DP .
    ### 备忘录有了, 我们尝试根据递推公式 :
    # coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))
    ### 书写状态转移方程 :

    s = {} # 设 s 为状态数组 :
    s[1] ,s[2] ,s[3] ,s[4] ,s[5] = 1,2,1,2,1

    def minCoinDP(money):
        for i in range(6,money+1):
            s[i] = 1+ min(s[i-1],s[i-3],s[i-5])

        return s[money]


    print(minCoinDP(10000))
    2019-03-13
    7
  • 攻玉
    import numpy as np
    老师 , 那个回溯法的代码好像不太对 , 我用 python 写了一个
    import sys
    minDist = sys.maxsize
    n = 4 # 这是个 4*4 的矩阵 .
    w = np.array([[0,3,5,9],[2,1,3,4],[5,2,6,7],[6,8,4,3]])
    # dist = np.zeros((4,4)) # 定义 dist(i, j) 为到达点 (i,j) 的路径长度
    # dist[i, j] = w[i,j] + min(dist[i-1, j] , dist[i, j-1])

    def minDistBackTrace(i, j, dist, w, n):
        global minDist
        dist += w[i][j]
        if i==n -1 and j == n-1 :
            if dist < minDist: minDist = dist
            return

        if i < n-1:
            minDistBackTrace(i + 1, j, dist, w, n)
        if j < n-1:
            minDistBackTrace(i , j + 1, dist, w, n)

    2019-03-12
    2
    3
  • 猫头鹰爱拿铁
    看了这一篇豁然开朗,上一篇的习题也会做了。感觉这些涉及多决策的习题基本上第一眼都能想到回溯法,但是用动态规划法就要好好想一想,关键还是老师说的动态转移方程式。我尝试用两种方法做了一遍,回溯法和动态规划法。

    int minNum = Integer.MAX_VALUE;

    /**
    * 使用回溯法获取给定金额最小的硬币数量,调用时num为0
    *
    * @param coinVal
    * 硬币值数组
    * @param total
    * 指定的金额
    * @param num
    * 每个解法所得到的硬币数量
    */
    public void getLeastCoinNumByBackTracking(int[] coinVal, int total, int num) {
    if (total == 0) {
    if (num < minNum)
    minNum = num;
    return;
    }
    for (int i = 0; i < coinVal.length; i++) {
    if (total - coinVal[i] >= 0) {
    getLeastCoinNumByBackTracking(coinVal, total - coinVal[i],
    num + 1);
    }
    }
    }

    /**
    * 使用动态规划法获取给定金额下最小的硬币数量
    *
    * @param coinVal
    * 硬币值数组
    * @param total
    * 给定金额
    * @return 给定金额下最小的硬币数量
    */
    public int getLeastCoinNumByDP(int[] coinVal, int total) {
    // coinNum存放的是每个对应金额下最少硬币的最优解
    int coinNum[] = new int[total + 1];
    coinNum[0] = 0;
    //初始化coinNum数组,硬币值数组对应的值的硬币数量都为1
    for (int i = 0; i < coinVal.length; i++) {
    coinNum[coinVal[i]] = 1;
    }

    for (int i = 1; i <= total; i++) {
    if (coinNum[i] == 0) {
    int minTemp = Integer.MAX_VALUE; // 获取每个i对应的最小硬币数值
    for (int j = 0; j < coinVal.length; j++) {
    if (i - coinVal[j] > 0) {
    int v1 = coinNum[i - coinVal[j]] + 1;
    if (v1 < minTemp) {
    minTemp = v1;
    }
    }
    }
    coinNum[i] = minTemp;
    }
    }
    return coinNum[total];
    }
    2019-01-08
    3
  • 菜菜
    老师,回溯法求矩阵最短路径的代码会出错,边界条件的问题
    2019-03-05
    2
  • 随风

    看了这么久,很少留言、很多思考题也只停留在想的层面,很少去实现。刚好有点时间,把动态规则这个思考题想了一下,顺便用Java实现出来。
    思考题:如上面值{1,3,5}凑9块钱的最小张数、我们可以分成3个阶段。
    第一阶段:用1块钱,那么1块钱可以有1、2、3...9张这几种可能。
    第二阶段:在第一阶段的金额还有张数上增加3元的
    第三阶段:在第二阶段总金额上载增加5元的。
    状态转移方程:Sum(n) = Sum(n-1) + v * num ,v表示当前阶段的面值,num表示当前阶段的张数。
    代码实现如下:
    public class DynMoney {
    private static int minNum = Integer.MAX_VALUE;
    /**
    * Sum(n) = Sum(n-1) + v * num
    * @param sum 凑的总额
    * @param v 钱的面额
    * @return
    */
    public static int minMoney(int sum,int v[]) {
    nextStep(0, 0, 0, sum, v);
    return minNum;
    }
    /**
    * @param n 钱的张数.
    * @param c 到那个阶段
    * @param cv 凑的钱数
    * @param sum 要凑的钱的总数
    * @param v 面额
    */
    public static void nextStep(int n,int c, int cv,int sum,int v[]) {
    //金额凑够了
    if (cv == sum) {
    minNum = Math.min(minNum, n);
    return;
    }
    //或者凑到最后阶段,没凑够总金额
    if(c == v.length) {
    return;
    }
    //每个阶段,钱的张数,张数应该小与等于 凑的金额/面额
    for(int j=0; j <= sum/v[c]; j++) {
    if(cv + v[c]*j <= sum) {
    //当前阶段凑的不超额,下阶段继续凑
    nextStep(n+j, c+1,cv + v[c]*j, sum,v);
    }
    }
    }

    public static void main(String arg[]) {
    System.out.println(minMoney(8, new int[]{1,3,5}));
    }
    }
    2019-02-14
    1
    2
  • Kudo
    思考题解答
    使用回溯法(python实现):
    import sys
    min_count = sys.maxsize # 用于追踪最小值

    def minCoinCount(i, values, amount, ca):
        '''
        i: 硬币数量
        values: 硬币面值数组
        amount: 要凑的总价值
        ca: current amount 当前价值
        '''
        global min_count
        if ca == amount or i == amount: # 总共amount步
            if ca == amount and i < min_count:
                min_count = i
            return
            
        for v in values: # 依次考察每种币值
            if ca + v <= amount: # 保证不超总值价
                minCoinCount(i+1, values, amount, ca+v)
                
    # 使用方法
    values = [1,3,5]
    minCoinCount(0, values, 9, 0)
    print(min_count)
    2019-01-04
    2
  • blacknhole
    状态转移方程法的代码实现有问题:
    1,int minUp = Integer.MIN_VALUE;语句应赋值为Integer.MAX_VALUE。
    2,返回前应将返回值赋值给mem[i][j]。

    作者回复: 已改 多谢指正

    2018-12-31
    2
  • Monday
    2018最后一次更新,我通读三遍跟上打卡了。本节理论归纳的很精简,适合动态规划求解的问题的特性:一个模型,三个特征。
    一个模型:多阶段决策最优解
    三个特征:最优子结构,无后效性,重复子问题。
    2018-12-31
    2
  • 想当上帝的司机
    放假了还在更新 赞
    2018-12-31
    2
  • 乾坤瞬间
    我捋一下思路用 状态转移表法
    1,首先这个问题适合用多阶段决策最优模型,不过唯一与前面的例子不同的是,这里的阶段不是很容易找,其实问题的期望实质上是保证走尽量少的阶段达到累计值到达期望值(9),而我们前面接触的都是固定的阶段,所以从这一点上对动态规划的阶段概念又有了新认识
    2,状态的定义,定义一个status[i][w]二维数组,i代表第i阶段,w表示第i阶段的累积值,且w不大于9.其实我把每一层的状态值定义为上一层的所有状态与本层的任一组合(1,3,5)的和这样我们就可以避免重复子结构(3->5与5->3的第二阶段的状态值都是8)的计算


    2019-11-24
    1
    1
  • 辣么大
    老师给的回溯法例子中边界的确有些问题。下面贴上修改后的实现:
      /**
       * call minDist(0, 0, a[0][0], a, a.length)
       * @param i cur row index
       * @param j cur column index
       * @param dist cur distance,start from a[0][0]
       * @param a array
       * @param n length of the input array
       */
      public static void minDistBt(int i, int j, int dist, int[][] a, int n) {
        System.out.printf("%2d %2d\n", i, j);
        if (i == n - 1 && j == n - 1) {
          if (dist < minDist)
            minDist = dist;
          return;
        }

        if (i + 1 < n)
          minDistBt(i + 1, j, dist + a[i + 1][j], a, n);

        if (j + 1 < n)
          minDistBt(i, j + 1, dist + a[i][j + 1], a, n);

      }
    2019-11-17
    1
  • am
    Go语言实现找零钱(动态规划)版本:

    // value: 硬币币值, n: 硬币数量, w: 支付金额
    func lfchange(value []int, n int, w int) int {
    sort.Ints(value)
    // 最小币值
    minV := value[0]
    // dp[i]表示支付金额为i需要多少个硬币
    dp := make([]int, w+1)
    for _, v := range value { // 初始化状态
    if v > w {
    break
    }
    dp[v] = 1
    }
    // 硬币数
    var count int
    for i := minV + 1; i <= w; i++ { // 动态规划方程转移
    count = 0
    for j := n - 1; j >= 0; j-- {
    if i%value[j] == 0 {
    dp[i] = i / value[j]
    break
    }
    }
    for j := minV; j < i; j++ {
    if dp[j] != 0 && dp[i-j] != 0 {
    count = dp[j] + dp[i-j]
    if count < dp[i] {
    dp[i] = count
    }
    }
    }
    }
    return dp[w]
    }
    2019-11-14
    1
  • 嘉一
    课后题答案(ts版本):
    class SortClazz {

                public static optionCell: number[] = [1, 3, 5];
                public static storeVal: { [key: number]: number } = {};

                public static getMinCount(targetVal: number): number {
                    let optionCell = SortClazz.optionCell;
                    if (optionCell.indexOf(targetVal) >= 0) {
                        return 1;
                    }
                    if (SortClazz.storeVal[targetVal]) {
                        return SortClazz.storeVal[targetVal];
                    }

                    let minArr: number[] = [];
                    for (let i = 0, leng = optionCell.length; i < leng; ++i) {
                        let tempVal = targetVal - optionCell[i];
                        if (tempVal > 0) {
                            minArr.push(SortClazz.getMinCount(tempVal));
                        }
                    }
                    let minVal: number = targetVal;
                    while (minArr.length > 0) {
                        minVal = Math.min(minVal, minArr.pop());
                    }
                    SortClazz.storeVal[targetVal] = ++minVal;
                    return minVal;
                }

            }
    2019-10-15
    1
  • Bayes
    思考题:
    个人感觉使用转移方程的思路比转移表更加清晰。这里使用递归+备忘录讲一下我的思路:
    凑够9元需要用最少的硬币:f(9)=min(5+f(4), 3+f(6), 1+f(8)),
    f(4)=min(3+f(1), 1+f(3)),
    f(6)=min(5+f(1), 3+f(3), 1+f(5)),
    f(8)=min(5+f(3), 3+f(5), 1+f(7)),
    f(7)=min(5+f(2), 3+f(4), 1+f(6)),
    f(2)=1+f(1),

    注:其中的f(1)、f(3)、f(5)可以看做是哨兵,结果都是1。
    2019-08-12
    1
  • Paul Shan
    思考题的递归式子是f(w) = min(f(w-1), f(w-3),f(w-5)) + 1,可以递归解决。
    2019-07-29
    1
收起评论
73
返回
顶部