先貼問題：
- Delete Operation for Two Strings
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
說白了就是找到兩個字符串非連續(xù)最大公共字符串滔蝉。如果對dp算法很熟悉的很快就能想到這個問題的解法，然而我并不是很熟悉噪生，所以用了一個很挫很慢的方法阵翎，個人理解應該是分治法逢并，很多步驟被重復算了很多次之剧。
寫的很搓，輕噴砍聊。
下面就要介紹一下簡單易懂的dp算法啦背稼，先上代碼（leetcode里大神寫的，我只是用golang重寫一遍）
思路很簡單辩恼，比如 word1=abcd，word2=obdce谓形。
用一個二維數組保存計算的值（代碼里多加了一行和一列置0方便計算)
比如比較word1的c和word2的c的時候灶伊，因為ab和obd的最大相同是1，所以這個位置上只需要dp[i-1][j-1]+1
動態(tài)規(guī)劃和分治區(qū)別:
動態(tài)規(guī)劃：它通常用于求解具有某種最優(yōu)性質的問題寒跳。在這類問題中聘萨，可能會有許多可行解。每一個解都對應于一個值童太，我們希望找到具有最優(yōu)值的解米辐。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題书释，先求解子問題翘贮，然后從這些子問題的解得到原問題的解。與分治法不同的是爆惧，適合于用動態(tài)規(guī)劃求解的問題狸页，經分解得到子問題往往不是互相獨立的。
分治法：若用分治法來解這類問題扯再，則分解得到的子問題數目太多芍耘，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案熄阻，而在需要時再找出已求得的答案斋竞，這樣就可以避免大量的重復計算，節(jié)省時間秃殉。我們可以用一個表來記錄所有已解的子問題的答案坝初。
注：不管該子問題以后是否被用到，只要它被計算過钾军，就將其結果填入表中脖卖。這就是動態(tài)規(guī)劃法的基本思路。
這一題算是讓我對動態(tài)規(guī)劃有一個更深的印象巧颈，故記錄一下畦木。以前雖然會寫，但是每次遇到問題都不會想不到去用砸泛，還是自己疏于練習十籍。
紙上得來終覺淺蛆封，絕知此事要躬行呀。
