看來flag有點沒有立好，我這兩天才寫了三道題。

軍艦這道題是一個常規(guī)問題，分割等和子集和完全平方數(shù)是動態(tài)規(guī)劃問題。

這么小的聲音還想開軍艦！

軍艦

這道題比較常規(guī)，因為軍艦之間兩兩通過空白分隔，所以我們直接從左上角開始遍歷，在遍歷的過程中記錄當(dāng)前的位置是否被訪問，如果訪問了直接跳過。如果當(dāng)前的元素是X，則向下或者是向右找。

為什么可以直接向下或者是向右？因為我們會記錄每個元素是否被訪問，不會出現(xiàn)訪問到一個【軍艦】中部的情況，一定是當(dāng)前的軍艦的第一個元素。

代碼如下：

分割等和子集

這種題目的第一反應(yīng)就是通過DFS實現(xiàn)。題目要求需要將數(shù)組分割成兩個等和子集，那么首先當(dāng)前數(shù)組一定得是偶數(shù)。所以我們只需要DFS遍歷所有的可能性，選擇或者不選擇當(dāng)前元素即可。

不過 ，在這里可以思考一個問題。題目只要求返回最后的結(jié)果，沒有要求中間的過程，這樣使用DFS記錄中間過程的思路其實不占優(yōu)，那么我們可以使用左程云交的思路，將DFS過程優(yōu)化成DP來做。

遞歸過程可以使用這樣的遞歸樹，遞歸樹定義的不同會導(dǎo)致最后使用DP數(shù)組的遞推順序不同。我們定義dfs中有兩個參數(shù)，一個是當(dāng)前的使用的元素下標(biāo)，另外一個是最大的【容量】。這里使用簡單的例子「1，2，3」為例，假設(shè)使用1元素，則剩余2，

dfs參數(shù)變成dfs(1,2)? 。通過整理遞歸樹，發(fā)現(xiàn)當(dāng)所有的元素都使用時，【容量溢出】得到dfs(3，-3)，但是不使用3時，可以得到dfs(3,0) 這個解成立。dfs(3,0)就可以理解為遍歷完所有的元素時，可以使容量為0。

通過以上的分析我們就需要初始化dp數(shù)組。在dfs時，當(dāng)下標(biāo)等于數(shù)組長度是結(jié)算結(jié)果，并且開始的狀態(tài)需要考慮【容量】為0，所以dp[數(shù)組長度+1][最大容量+1]，這樣我們就可以使用dp[0][容量]返回結(jié)果。

因為dp[最大容量][0]是可行結(jié)果，需要初始化為true。

而且分析遞歸樹我們可以得出狀態(tài)轉(zhuǎn)移公式：

dp[i][j] = dp[i+1][j-num[i]] or dp[i+1][j]

計算方向是從左下到右上。

那么，這個【背包問題】我們就從dfs優(yōu)化成了dp問題。

完全平方數(shù)

這道題比較簡單。遞歸樹如下：

容易發(fā)現(xiàn)，當(dāng)前的數(shù)字基于前面的計算的結(jié)果中的最小值，直接上dp：

感覺dp背包問題還不是很熟，明天繼續(xù)寫?。。。?奧利給干了！