线性DFS理解 线性dfs的理解:
1，例子
输入一个n,输出以n开始的所有严格递减序列的个数，例如：当n=3时，以n开始的严格递减序列有：(3,2),(3,1),(3,2,1) 。
样例：
input:
3 output:
3 怎么样求解这个问题，想必大家已经有了自己的解题思路，但是小编现在这里讲一下小编的做法：
小编喜欢dfs暴搜，所以小编的第一想法就想到dfs 。
【线性DFS理解】解题代码
#include using namespace std;int n;int cnt=0;void dfs(int a,int b){ cnt=cnt+1;// dfs()函数执行一次都对应一个序列 for(int i=1;i<=n;i++)//b后面的点的可能取值if(i>n; for(int i=1;i 问： 不是说好的dfs吗，为什么没有回溯？
小编： 对呀，怎么样理解这个问题?
理解：是不是所有的dfs都得回溯，对，每一个dfs算法都会回溯，但是回溯的方式各不相同，比较常见的就是return,但是有一些题目隐藏的调节会使得函数自己回溯，就像这个题目，当所在点不在满足条件时，会自动回溯到上一层 。
线性dfs的运用:
这题上蓝桥杯模拟赛的倒数第二题：
题解：
#include #include using namespace std;int cnt=0;int n;void dfs(int a,int b){ cnt=cnt+1; int t=abs(a-b);//控制下一个点的条件 for(int i=1;i<=n;i++)if(i>n; for(int i=1;i<=n;i++)dfs(n,i); cout< 但是这个做法无法在赛场上过调所有的数据
优化方向：记忆化搜索 。