Open tinyyard opened 10 years ago
1、计算边界条件的时候计数器应该从0开始吧，这样才能给dp[0][0]赋值，否则在最后计算编辑距离的循环中，如果pSource[0] == pTarget[0]， 则dp[1][1] = dp[0][0]，此时dp[0][0]值未知。虽然我用的java重写的版本中，编译器自动给数组中未赋值的元素置0了，但是，整形数组初始值是根据编译环境不同有差异的吧。 2、在计算编辑距离的嵌套循环中，如果pSource[i - 1] != pTarget[j - 1]，也就是在else{}中，dp[i][j]应该等于dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j-1]三者中的最小值 +1，java中实现是dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; 因为此时是删除、增加、替换操作三者选一，代码中dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);应该指的是编辑距离中只有删除和增加两种操作的情况。
这个是我用java重新实现了算法之后的结论撒~如果有什么地方想得不对请多多指教~
1、计算边界条件的时候计数器应该从0开始吧，这样才能给dp[0][0]赋值，否则在最后计算编辑距离的循环中，如果pSource[0] == pTarget[0]， 则dp[1][1] = dp[0][0]，此时dp[0][0]值未知。虽然我用的java重写的版本中，编译器自动给数组中未赋值的元素置0了，但是，整形数组初始值是根据编译环境不同有差异的吧。 2、在计算编辑距离的嵌套循环中，如果pSource[i - 1] != pTarget[j - 1]，也就是在else{}中，dp[i][j]应该等于dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j-1]三者中的最小值 +1，java中实现是dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; 因为此时是删除、增加、替换操作三者选一，代码中dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);应该指的是编辑距离中只有删除和增加两种操作的情况。
这个是我用java重新实现了算法之后的结论撒~如果有什么地方想得不对请多多指教~