Skip to content

Commit 4398080

Browse files
wisdompeakwisdompeak
authored
Update Readme.md
1 parent 788f296 commit 4398080

File tree

1 file changed

+3
-3
lines changed
  • Dynamic_Programming/072.Edit-Distance

1 file changed

+3
-3
lines changed

‎Dynamic_Programming/072.Edit-Distance/Readme.md‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
### 072.Edit-Distance
22

3-
此题类似097.Interleaving String，用DP来实现两个数组的某项功能关系。dp[i][j]分别表示数组A取前i位、数组B取前j位时的目标函数，想办法找出其与dp[i-1][j]或dp[i][j-1]或dp[i-1][j-1]或以上所有的递推关系。
3+
此题类似097.Interleaving String，用DP来实现两个数组的某项功能关系。用dp[i][j]分别表示数组A取前i位、数组B取前j位时的目标函数，想办法找出其与dp[i-1][j]或dp[i][j-1]或dp[i-1][j-1]或以上所有的递推关系。
44

5-
对于dp[i][j]，常规思路是考虑数组A的第i位，数组B的第j位。一个最直接的想法是：如果word1[i]==word2[j]，那么显然dp[i][j]=dp[i-1][j-1]，轻而易举地把锅甩给了低一个量级的子问题。那么如果如果word1[i]!=word2[j]呢？显然想递进到dp[i][j]的话，可以从dp[i-1][j]入手，将word1[i-1]接上word2的第j个字符即可匹配成功；或者从dp[i][j-1]入手，将word2[j-1]接上word1的第i个字符即可匹配成功；第三个方案是从dp[i-1][j-1]入手，将word1的第i个字符直接替换为word2的第j个字符，同样可以使两者匹配成功。
5+
对于dp[i][j]，常规思路是考虑数组A的第i位，数组B的第j位。一个最直接的想法是：如果word1[i]==word2[j]，那么显然dp[i][j]=dp[i-1][j-1]，轻而易举地把锅甩给了低一个量级的子问题。那么如果如果word1[i]!=word2[j]呢？显然，若想递进到dp[i][j]的话，可以从dp[i-1][j]入手，将word1[i-1]接上word2的第j个字符即可匹配成功；或者从dp[i][j-1]入手，将word2[j-1]接上word1的第i个字符即可匹配成功；第三个方案是从dp[i-1][j-1]入手，将word1的第i个字符直接替换为word2的第j个字符，同样可以使两者匹配成功。
66

77
综上，粗浅的递推关系很容易写出来（以1为index的起点）：
88
```cpp
@@ -17,4 +17,4 @@ for (int i=1; i<=n1; i++)
1717
```
1818
输出的结果是dp[n1][n2].
1919
20-
现在考虑初始条件。发现当i=1, j=1时，上述递推关系式中需要用dp[i][0] (for all i), dp[0][j] (for all j). 因此我们特别考虑一下他们。很明显dp[i][0]表示子串A有i位，子串B有零位，显然只需要在子串添加i个相应的字符即可匹配字符串A，所以dp[i][0]=i。同理，dp[0][j]=j。更特殊一点，dp[0][0]=0.
20+
现在考虑边界条件。发现当i=1, j=1时，上述递推关系式中需要用dp[i][0] (for all i), dp[0][j] (for all j). 因此我们特别考虑一下他们。很明显dp[i][0]表示子串A有i位，子串B有零位，显然只需要在子串添加i个相应的字符即可匹配字符串A，所以dp[i][0]=i。同理，dp[0][j]=j。更特殊一点，dp[0][0]=0.

0 commit comments

Comments
 (0)