先貼問題：
- 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算法很熟悉的很快就能想到這個問題的解法，然而我并不是很熟悉，所以用了一個很挫很慢的方法，個人理解應(yīng)該是分治法，很多步驟被重復(fù)算了很多次。
寫的很搓，輕噴。
下面就要介紹一下簡單易懂的dp算法啦，先上代碼（leetcode里大神寫的，我只是用golang重寫一遍）
思路很簡單，比如 word1=abcd，word2=obdce。
用一個二維數(shù)組保存計(jì)算的值（代碼里多加了一行和一列置0方便計(jì)算)
比如比較word1的c和word2的c的時候，因?yàn)閍b和obd的最大相同是1，所以這個位置上只需要dp[i-1][j-1]+1
動態(tài)規(guī)劃和分治區(qū)別:
動態(tài)規(guī)劃：它通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。
分治法：若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。
注：不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。
這一題算是讓我對動態(tài)規(guī)劃有一個更深的印象，故記錄一下。以前雖然會寫，但是每次遇到問題都不會想不到去用，還是自己疏于練習(xí)。
紙上得來終覺淺，絕知此事要躬行呀。
