一点dfs搜索小结
首先说说两个经典的搜索策略，dfs和bfs，dfs对于是按照深度进行搜索，它主要就是对于当前可行节点马上扩展，直到不可行的那个节点，那么就进行回朔，那么在回朔那里我们可以保存全局变量的值，以便供其他中可行的方案进行扩展，那九宫格来说，也就是数独游戏，
现在我们按照dfs来遍历，假设我们从dfs（0,0)开始，然后按行进行扩展，如果当前已经有值，那么我们递归进入下一个节点，而对于本层次我们要保存一些信息，比如此时map里放入的具体值是多少，因为我们不知道此次递归是否是正确的递归，如果不正确的话，我们还要在这里回朔，如果当前没有值，那么我们一次从1...9进行试探，对于可行的节点马上进入下一次递归，当然这里同样要保存节点信息，以便下一次回朔！
我们知道对于搜索来说，一开始的时候，往往具有很多分支，往往是有多种可能性，但是随着递归深度的增加，分支数就会逐渐减少，然后最后就可能出现满足条件和不满足条件的情况，对于满足条件的情况，那么我们就可以直接退出了，表示我们已经搜索到了我们要的结果，可以退出了，同样，如果不满足条件，那么我们知道，此时是不行的，那么我们想回到上一层的递归，此时就要回朔了，但是此时如果我们没有对于递归的临时栈没有保存的话，那么我们也不会知道何时应该回朔，何时是正确结果本该退出！所以一般来说，这里往往是需要一个临时变量来保存下一次递归的结果，然后根据这个结果，来决定是回朔，还是已经是正确的结果可以退出了！ 此时往往是这样 对于 dfs(i) 那么var=dfs(i+1)，如果。。否则又，这里要注意的是，因为在一开始我们可能对于每一层递归都有很多种情况，所以在回朔的时候，一定要注意回朔的位置一定要是相应的位置！
1.poj1011 sticks 经典的一题，是我一开始的一题
我的大体思路是这样：
1.首先对于可能的长度len，首先求出总共的棍的数目num，然后对len
进行dfs，在数组里找合适的木棍填充len，填充完毕后，num数减少1，在继续在里面找，
如果在当前层次上面找不到后，那么就退出此时的查找，说明len是不可能的长度(这里要对数组
元素降序排序。。
这里问题就是如何每一次对len的dfs，找出合适的棍子，以及如果不合适，怎么回到上一层
这里主要的是考察优化的
2.poj 2362 这一题和sticks一题很相似
思路大致是这样，首先判断棍子是否能被4正除，若能，求出棍子的长度，然后在里面找起组合，若能组成4条这样的那么就行了
3. 素数环，这一题就是简单的dfs了，非常好写，只要满足相邻数的和就可以继续扩展了！
4. poj1416 对于这一题，要求是分解一个数，要他们的和，比目标数小而且最好是尽量接近，而要用dfs搜索的话，这里每一层涉及到的递归信息比较多，因为要多次求值，每次我们都要保存一些临时的值，对于这些递归来说，在某些层次递归的步骤比较多，我们往往会在递归的条件里在套一个递归，对于这些，理解起来会有难度，一个好的做法就是在每一部递归的过程中输出相应的临时变量，这样便可以跟踪递归时一些量的变化！这个题目到目前还没有解决，只有过几天再看看了，主要原因是dfs的过程中设计到的临时变量很多，不知道如何来设计这个回朔！
———————————————————————————————————————
具体代码在我的csdnhttp://blog.csdn.net/pzz837157806?viewmode=contents