Golang | Dynamic Programming With Explanation🚀
Intuition\nWe will have to draw a table to help understand how DP works in this solution:\n\n||empty str|r|o|s|\n|:-:|:-:|:-:|:-:|:-:|\n|empty str|0|1|2|3|\n|h|
# Intuition\nWe will have to draw a table to help understand how DP works in this solution:\n\n||empty str|r|o|s|\n|:-:|:-:|:-:|:-:|:-:|\n|empty str|0|1|2|3|\n|h|1|1|2|3|\n|o|2|2|1|2|\n|r|3|2|2|2|\n|s|4|3|3|2|\n|e|5|4|4|**3**|\n\nIn this table, the number in the cells stands for **the minimum operation times** needed to transform from `word1` to `word2`. Note we only care about the first `n` chars when we fill the `nth` row or cols!\n\nFor example, we only care about `hor` when we are dealing with `row \'r\'`.\n\nMore specifically:\n1. In `row \'h\'`, `col \'r\'`, we only care about how to transform from \'h\' to \'r\'.\n2. In `row \'o\'`, `col \'r\'`, we only care about how to transform from \'ho\' to \'r\'.\n3.  In `row \'r\'`, `col \'o\'`, we only care about how to transform from \'hor\' to \'ro\'.\n4. ... I believe you get the point! \uD83D\uDE0A\n\nWhat we will do is to find a way to quickly fill the table! The number in the bottom-right of the table will be our answer.\n\nWhen you mannually fill this table, I believe you can find some certain rules:\n+ the number in the first col (i.e. `col \'empty str\'`) always equals to the **row index**. This is because we need to remove every char in `word2` to get a empty `word1`!\n+ If the last char of `word2` is identical to the last char of `word1`, the operation number should be the same as `table[i-1][j-1]` (just imagine we are dealing with `table[i][j]`)! This is because **if the last char of the two words are the same, we need no more extra operation**!\n+ If the last char of `word2` is different from the last char of `word1`, we will have to look at these 3 cells: `table[i][j - 1]`, `table[i - 1][j - 1]` and `table[i - 1][j]`. We will fill `table[i][j]` with the minimum number plus 1. This is because **we have to deal with this char difference (plus 1), and we will choose the optimal way to conduct the former transformation**!\n\n# Code\n```\nfunc minDistance(word1 string, word2 string) int {\n    pre := make([]int, len(word2) + 1)\n    cur := make([]int, len(word2) + 1)\n    for i := 0; i < len(pre); i++ {\n        pre[i] = i\n    }\n    for i := 1; i <= len(word1); i++ {\n        cur[0] = i\n        for j := 1; j < len(pre); j++ {\n            if word1[i - 1] != word2[j - 1] {\n                cur[j] = min(cur[j - 1], pre[j - 1], pre[j]) + 1\n            } else {\n                cur[j] = pre[j - 1]\n            }\n        }\n        tmp := make([]int, len(cur))\n        copy(tmp, cur)\n        pre = tmp\n    }\n    return pre[len(word2)]\n}\n\nfunc min(nums ...int) int {\n    ans := nums[0]\n    for _, v := range nums {\n        if v < ans {\n            ans = v\n        }\n    }\n    return ans\n}\n```
['Dynamic Programming', 'Go']