精选留言(14)

• 
  Ares

  2019-05-02

  老师视频中应该讲反了：
  dp[i-1][j] + 1 应该是删除操作；
  dp[i][j-1] + 1 应该是增加操作。

  

   6
• 
  Don

  2018-12-26

  老师我怎么觉得dp[i-1,j]是删除一个字符呢，如果是从i变到j的话，dp[i,j-1] 是增加一个字符。

  

   2
• 
  sourcesC

  2018-12-18

  老师,为什么插入是dp[i-1][j],删除是dp[i][j-1]? 我的理解是在word1上插入元素的话就是(i,j-1) 因为插入的元素肯定和word2[j]相等,所以在word2上索引减1; 而删除的话是(i-1,j),因为word1上少一个元素,所以i-1,而删除之后word1[i-1]不一定和word[j]相等,所以j不减; 不知我的理解是否有问题

  

   1
• 
  Heimerdinger

  2018-11-29

  数组初始化的时候为什么是 range(m+1)呢

  作者回复: 因为最后那个元素要放在 a[m] 里

  

   1
• 
  Aliliin

  2019-12-04

  PHP. 解法：
  
   function minDistance($word1, $word2) {
          $edit = [];
          $w1 = strlen($word1);
          $w2 = strlen($word2);
          for ($i = 0; $i <= $w1; ++$i) $edit[$i][0] = $i;
          for ($j = 0; $j <= $w2; ++$j) $edit[0][$j] = $j;
          for ($i = 1; $i <= $w1; ++$i) {
              for ($j = 1; $j <= $w2; ++$j) {
                  $flag = $word1[$i - 1] == $word2[$j - 1] ? 0 : 1;
                  $edit[$i][$j] = min($edit[$i][$j - 1] + 1, $edit[$i - 1][$j] + 1, $edit[$i - 1][$j - 1] + $flag);
              }
          }
          return $edit[$w1][$w2];
      }

  展开

  

  
• 
  关

  2019-11-15

  讲解一些递推公式的推断理解过程：word1删除第i个元素那么DP[i][j] 就转化为了DP[i-1][j]+1 ；word1在第i+1个位置插入word2的第j个元素，那么DP[i][j] 就转化为了DP[i][j-1] +1 （[i+1] ==[j]） ；word1 的[i]个元素替换为word2[j] 则 DP[i][j] 就转化为了DP[i-1][j-1]+1 同理分析word2的删除插入替换。
  
  求大神指出思维误区，我看了一下leetcode的官方思路也是很难理解

  展开

  

  
• 
  关

  2019-11-14

  讲问题应该讲清楚 别敷衍 剪来剪去思路都不连贯了 是来学习思维的 大哥

  

  
• 
  Sun0010

  2019-10-23

  如果 w1[i] == w2[j] : (i-1,j-1)
           else
       1.替换 步数加1, 这个时候肯定相等然后各自往前走一步， 就 DP(i-1,j-1) + 1
       2.删除 第i个位置的字符 步数 + 1, 那么就变成DP(i-1,j) + 1 来比较
       3.插入 在第i+1个位置插入 w2[j], 这个时候 word1 还是 前i个字符，但是这个时候 w1[i+1] == w2[j]
         ，这个时候肯定相等然后各自往前走一步，所以 DP[i][j-1] + 1

  展开

  作者回复: Good！

   1

  
• 
  陈志恒

  2019-09-28

  1.dp解决“字符串匹配”的“状态定义trick”，并且有复杂的“ifelse转移方程”
  2.一般情况：状态是几维的，复杂度一般是几次

  

  
• 
  打奥特曼的小怪兽

  2019-08-29

  Java 最朴素的DP
  class Solution {
      public int minDistance(String word1, String word2) {
          int w1 = word1.length();
          int w2 = word2.length();
          
          //边界条件-对任意的空字符串的处理
          if(w1*w2 == 0){
             return w1 > w2 ? w1 : w2 ;
          }
          int[][] dp = new int[w1+1][w2+1];
          
          for(int i=1;i<=w1;i++){
             //初始条件设置
             dp[i][0] = i;
             for(int j=1;j<=w2;j++){
                //初始条件设置
                dp[0][j] = j;
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                   dp[i][j] = dp[i-1][j-1];
                }else{
                   dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                }
             }
          }
          return dp[w1][w2];
      }
  }

  展开

  作者回复: Coool!

  

  
• 
  Zix

  2019-05-26

  老师好，请教一个问题。
  当word1[i] = word2[j] 的时候，状态转移方程老师在讲述的时候 dp[i][j] = dp[i-1][j-1]; 但是在代码实现的时候确是 dp[i][j] = min(dp[i-1][j-1],dp[i][j-1]+1,dp[i-1][j]+1);
  我用的cpp实现的，这两种写法均可在leetcode上ac。这就有点不解了，请老师说明一下区别，是不是因为测试用例太少的原因才导致两者一致。

  展开

  

  
• 
  极客时间

  2019-03-17

  代码中的三目运算符，替换操作也要+1吧

  

  
• 
  hkhkhkhk_1993

  2019-01-09

  python有个小坑 一开始赋值的时候如果写成dp = [[0]*(n+1)]*(m+1) 结果会不对 因为指向可变对象的关系 后面元素的更改会出现一改全改的情形

  

  
• 
  Heimerdinger

  2018-11-29

  数组初始化的时候为什么是 range(m+1)呢

  

  