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

精选留言(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