精选留言(17)

• 
  joy

  2018-12-30

  老师讲的很好，看了两遍动态规划这个系列，动态规划突然开窍了，感觉这个算法太牛了

  

   6
• 
  Don

  2018-12-24

  老师讲得思想方法很重要，递归--》存储--》递推
  现在看到能递归的就反着想，然后找上一步能保存到下一步的数据结构，越简单的越好。

  

   3
• 
  雷朝建

  2019-01-12

  写这道题时候， 我还没学习过动态规划， 然后我从上往下写， 但明显代码没有从下往上优美。
  JS版本（从上往下）：
  /**
   * @param {number[][]} triangle
   * @return {number}
   */
  var minimumTotal = function(triangle) {
    for (let i = 1; i < triangle.length; i++) {
      for (let j = 0; j < triangle[i].length; j++) {
        const prev = triangle[i - 1];
        const cur = triangle[i];
        if (j === 0) triangle[i][j] += prev[0];
        else if (j === cur.length - 1) triangle[i][j] += prev[prev.length - 1];
        else triangle[i][j] += Math.min(prev[j - 1], prev[j]);
      }
    }
    return Math.min(...triangle[triangle.length - 1]);
  };
  
  JS版本（从下往上）：
  /**
   * @param {number[][]} triangle
   * @return {number}
   */
  var minimumTotal = function(triangle) {
    const mini = triangle[triangle.length - 1];
    for (let i = triangle.length - 2; i >= 0; i--) {
      for (let j = 0; j < triangle[i].length; j++) {
        mini[j] = triangle[i][j] + Math.min(mini[j], mini[j + 1]);
      }
    }
    
    return mini[0];
  };
  
  被mini数组的设定震惊到了。

  展开

  

   1
• 
  预见

  2018-11-30

  使用一维数组来存储状态，动态更改该数组在每一层的值，实现O(n)复杂带。这个也太dynamic programming了吧！

  

   1
• 
  大头

  2019-12-04

  感觉是那么回事，写起来无从下手，还是需要多多练习啊

  

  
• 
  Aliliin

  2019-11-28

  PHP DP 自下而上的写法：
  
  
  function minimumTotal($triangle)
      {
          for ($i = count($triangle) - 2; $i >= 0; $i--) {
              for ($j = 0; $j < count($triangle[$i]); $j++) {
                  $triangle[$i][$j] = min($triangle[$i + 1][$j], $triangle[$i + 1][$j + 1]) + $triangle[$i][$j];
              }
          }
          return $triangle[0][0];
      }

  展开

  

  
• 
  邱

  2019-11-28

  这题让我脑洞大开，确实佩服。

  

  
• 
  陈志恒

  2019-09-28

  dp子问题、贪心局部最优区别：就像子树和子节点的区别

  

  
• 
  打奥特曼的小怪兽

  2019-08-29

  class Solution {
      public int minimumTotal(List<List<Integer>> triangle) {
          
          //dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j];
          int row = triangle.size();
          //与C++代码的区别，初始数组没有赋值最后一层的元素
          int[] dp = new int[row+1];
          
          //从最后一层开始
          for(int i=row-1;i>=0;i--){
             //遍历列
             for(int j=0;j<triangle.get(i).size();j++){
                //递推公式
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j],dp[j+1]);
             }
          }
          
          return dp[0];
      }
  }

  展开

  

  
• 
  ssala

  2019-05-25

  状态压缩

  

  
• 
  ssala

  2019-05-25

  这题很典型，逆向思维，从底部往上计算，想了下上一节爬楼梯是不是也可以从下楼梯的角度考虑？从而来理解递推公式。
  
  dp问题，问题建模仍然是关键，这题是二维的一个例子，前面爬楼梯是一维的例子。这题空间复杂度能降到O（n），爬楼梯空间复杂度能降到O（1）。dp问题，除了时间上的优化，也要根据问题进行空间上的优化。

  

  
• 
  DanielAnton

  2019-04-04

  留言长度限制，只有分开了，这是动态规划的
  动态规划：
  ```
      public static int minimumTotal(List<List<Integer>> triangle) {
          int level = triangle.size();
          List<Integer> min = new ArrayList<>(triangle.get(level - 1));
          for(int i = level - 2; i >= 0; i--) {
              int len = triangle.get(i).size();
              for(int j = 0, k = 0; j < len && k < len; j++, k++) {
                  int tmp = Math.min(min.get(k), min.get(k + 1)) + triangle.get(i).get(j);
                  min.set(j, tmp);
              }
              min.remove(min.size() - 1); // 每次重置后，最后一个就不需要了
          }
          return min.get(0);
      }
  ```

  展开

  作者回复: 赞👍
  

  

  
• 
  DanielAnton

  2019-04-04

  想法有了，但自己写折腾了好久，还是练的太少了，贴出来，有改进的地方希望提出来，大家共同学习~~
  
  自顶向下：
  ```
      public int minimumTotal(List<List<Integer>> triangle) {
          int level = triangle.size();
          return helper(triangle, 0, 0, level);
      }
      
      // 参数i表示当前层，level表示共有多少层
      public int helper(List<List<Integer>> triangle, int i, int j, int level) {
          if(i >= level || j >= triangle.get(i).size())
              return 0;
  
          int left = helper(triangle, i + 1, j, level);
          int right = helper(triangle, i + 1, j + 1, level);
  
          return Math.min(left, right) + triangle.get(i).get(j);
      }
  ```
  
  带备忘录的自顶向下：
  ```
      public static int minimumTotal(List<List<Integer>> triangle) {
          int level = triangle.size();
          List<List<Integer>> memory = new ArrayList<>();
          memory.add(new ArrayList<>());
          return helper(triangle, 0, 0, level, memory);
      }
      // 参数i表示当前层，level表示共有多少层
      public static int helper(List<List<Integer>> triangle, int i, int j, int level, List<List<Integer>> memory) {
          if(i >= level || j >= triangle.get(i).size())
              return 0;
          // 到了最后一层，就将结果全部放入
          if(i == level - 1 && memory.get(i).isEmpty()) {
              for(int k = 0; k < triangle.get(i).size(); k++)
                  memory.get(i).add(triangle.get(i).get(k));
          }
  
          if(!memory.get(i).isEmpty() && j < memory.get(i).size() && memory.get(i).get(j) != null)
              return memory.get(i).get(j);
  
          if(memory.size() < level) // 防止添加回溯的过程又添加
              memory.add(new ArrayList<>());
  
          int left = helper(triangle, i + 1, j, level, memory);
          int right = helper(triangle, i + 1, j + 1, level, memory);
          memory.get(i).add(Math.min(left,right) + triangle.get(i).get(j));
  
          return memory.get(i).get(j);
      }
  ```
  

  展开

  作者回复: 这种努力学习和动手的态度值得表扬！！
  

  

  
• 
  ...

  2018-12-20

  其实可以直接使用triangle本身的，不用额外申请数组
  ```
  class Solution:
      def minimumTotal(self, triangle):
          """
          :type triangle: List[List[int]]
          :rtype: int
          """
          for row in range(len(triangle) - 2, -1, -1):
              for j in range(len(triangle[row])):
                  triangle[row][j] = min(triangle[row + 1][j], triangle[row + 1][j + 1]) + triangle[row][j]
  
          return triangle[0][0]
  ```

  展开

  

  
• 
  邓桥

  2018-12-16

  老师，我自己怎么是从上到下递推的，这样有问题吗？

  作者回复: 上到下没法有效递推吧

  

  
• 
  Sun0010

  2018-12-02

  老师讲的非常好，动态倒推的3部曲
  1. 定义状态 dp[i][j] : 从底部到 triangel[i][j] 的路径的最小值
  2.转移方程式: dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]);
  3.定义初始化的值: dp[rowMax][j] = triangle[rowMax][j]
  
  我总感觉用二维数组存储更好理解，老师的代码里面是用 一维数组存储 最小值，感觉很N,但对于初学者 有点 看不太懂
  
  for (int i = rowMax-1; i >=0 ; i--) {
      for (int j = 0; j <=colMax && triange[i][j] >0 (假设 0是初始值) ;j ++ ) {
          dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]);
      }
  }
  return dp[0][0];
  

  展开

  作者回复: 对的，你用二维数组非常清晰。不过就是一维数组的好处是稍微节省内存。

  

  
• 
  zixuan

  2018-11-29

  这个记得当时叫滚动数组

  

  