我的狀態(tài)定義是：定義f(x)=A和B中長度為x的子序列的末尾

這里確實把問題規(guī)模變小了，也有了子問題，也可以從f(x-1)轉(zhuǎn)移出f(x)。

但有兩個問題：

1. 我不知道最終答案存儲在哪個狀態(tài)里。

2. f(x)的獲取依舊不明朗。

關于2，我的思考過程是這樣的：當x=1的時候，去尋找A跟B中第一個相等的元素就行了。當x=2，就需要從x=1的情況下，從第一個相等元素的位置往后遍歷，但是這樣的話，可能性就很多了，固定A的元素去遍歷B，或者固定B去遍歷A，哪一個可以得到最優(yōu)結(jié)果，在這種狀態(tài)定義下并不能判斷。而且，x=1的情況，未必是包含在最優(yōu)路徑中的。

怎么想怎么難受，而且用數(shù)組來存儲一個二維數(shù)組也很奇怪。

其實我的問題是：不能用最終答案來定義狀態(tài)，因為這樣相當于是把問題復讀了一遍。

動態(tài)規(guī)劃的本質(zhì)是把題目給出的信息做各種變形，從而更容易與最終答案連接，所以絕對不能用答案定義狀態(tài)，用終點連接終點，這樣是沒有意義的。

狀態(tài)的定義一定要基于題目給出的信息，這一點首先明確了；其次是狀態(tài)的轉(zhuǎn)移，一定要能夠明確的用幾種情況概括完所有可能的答案，如果不能，說明狀態(tài)定義有問題。

正面例子：

還是很抽象，第一種情況好理解，相等說明長度+1，答案更優(yōu)了，沒有疑問；但是第二種呢？說的是跳過，我的描述是把前面得到的最優(yōu)答案往后延續(xù)，外層循環(huán)是mxn的復雜度，每對元素都會訪問到，就是說哪怕刨開DP，其實也能夠得到所有情況了，DP的角色只是存儲中間信息，并沒有把問題本身變簡單。

舉個例子：

A=[1,7,7,7,7,7] B=[0,0,0,0,1,0,7]

兩個1隔了很遠，狀態(tài)轉(zhuǎn)移只轉(zhuǎn)移相鄰的狀態(tài)，那[1]這個子序列不就跳過了嗎，直覺上我是這么覺得的。哦，對了，i跟j未必是相等的啊，我老是覺得i=j，然后做狀態(tài)轉(zhuǎn)移，但是i≠j，換句話說[1]這個子序列會好好保存下來，并且后面如果沒有更長的序列，這個值會保留。

這樣就沒問題了。有一點想通了，感覺自己對于最優(yōu)子結(jié)構這一點還是缺少理解。

果然，看了那么多題解，也做了一些DP題目，完全沒找到什么共性。

背后的原因是寫題解的人。假如你要教一個人怎么拿起杯子，你不會強調(diào)每根手指怎么用力，因為這些已經(jīng)內(nèi)化到你的潛意識里了，你自己也不知道怎么用力。

就像我會用最終問題定義狀態(tài)一樣，習慣了DP的人根本不會這么做，也不理解為什么會有人這么做，因為用題目給出的信息來定義狀態(tài)，對于這些人來說是理所當然的。

最終，還是只能依靠自己的思考，把一些難以敘述的問題找出來。