看来flag有点没有立好，我这两天才写了三道题。

军舰这道题是一个常规问题，分割等和子集和完全平方数是动态规划问题。

这么小的声音还想开军舰！

军舰

这道题比较常规，因为军舰之间两两通过空白分隔，所以我们直接从左上角开始遍历，在遍历的过程中记录当前的位置是否被访问，如果访问了直接跳过。如果当前的元素是X，则向下或者是向右找。

为什么可以直接向下或者是向右？因为我们会记录每个元素是否被访问，不会出现访问到一个【军舰】中部的情况，一定是当前的军舰的第一个元素。

代码如下：

分割等和子集

这种题目的第一反应就是通过DFS实现。题目要求需要将数组分割成两个等和子集，那么首先当前数组一定得是偶数。所以我们只需要DFS遍历所有的可能性，选择或者不选择当前元素即可。

不过 ，在这里可以思考一个问题。题目只要求返回最后的结果，没有要求中间的过程，这样使用DFS记录中间过程的思路其实不占优，那么我们可以使用左程云交的思路，将DFS过程优化成DP来做。

递归过程可以使用这样的递归树，递归树定义的不同会导致最后使用DP数组的递推顺序不同。我们定义dfs中有两个参数，一个是当前的使用的元素下标，另外一个是最大的【容量】。这里使用简单的例子「1，2，3」为例，假设使用1元素，则剩余2，

dfs参数变成dfs(1,2)  。通过整理递归树，发现当所有的元素都使用时，【容量溢出】得到dfs(3，-3)，但是不使用3时，可以得到dfs(3,0) 这个解成立。dfs(3,0)就可以理解为遍历完所有的元素时，可以使容量为0。

通过以上的分析我们就需要初始化dp数组。在dfs时，当下标等于数组长度是结算结果，并且开始的状态需要考虑【容量】为0，所以dp[数组长度+1][最大容量+1]，这样我们就可以使用dp[0][容量]返回结果。

因为dp[最大容量][0]是可行结果，需要初始化为true。

而且分析递归树我们可以得出状态转移公式：

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

计算方向是从左下到右上。

那么，这个【背包问题】我们就从dfs优化成了dp问题。

完全平方数

这道题比较简单。递归树如下：

容易发现，当前的数字基于前面的计算的结果中的最小值，直接上dp：

感觉dp背包问题还不是很熟，明天继续写！！！！ 奥利给干了！