Question
输入n，满足要求的序列，第一个数为n，第二个数为n以下，第三个数与前两个数之差的绝对值以下，以后相同。 求几种序列？ 答案是10000 (数据： n最大1000 ) ) ) ) )。
Sample
输入：4/输出： 7
输入：5/输出： 14
输入：6/输出： 26
Hint
如果n为4，存在以下序列：
4 1
4 2
4 3
4 4
4 1 1
4 1 2
4 2 1
所以一共7种。
这是学校比赛的问题，当时用朴素的dfs施暴。 最多只能计算到n为30左右。 之后，我要等很长时间，这个问题n最多1000个。 听说比赛后是记忆化检索，有空还打算再讨论。 时隔几个月，终于重新审视了这个问题。 用记忆化搜索试试，调试了相当长时间，终于解决了。 此时，n为1000时，可以在2s内给出答案，但时限1s仍然超时，可以进一步优化。 结合这个问题总结一下记忆化检索吧。
由于典型的搜索效率低下，通常在数据较大时会发生TLE。 一个重要原因是在搜索过程中重复计算了重复子问题。 记忆化检索是在检索的形式上加入了动态规划的思想，在遇到重复计算增多的问题时，在检索中记录一些状态的回答，可以减少重复检索量。 存储检索本质上是DP，它们都存储中间结果，不同之处在于，DP从下向上计算，而存储DFS从上到下计算，因为它们是递归的。
记忆化搜索：
递归函数的结果作为返回值存在，不能作为全局变量或参数传递。 不依赖于外部变量。
(根据上述两个要求写朴素的dfs检索后，添加存储数组即可)存储数组一般初始化为-1。 在各状态搜索的开始进行判断，如果该状态已经计算出，则直接返回回答，否则进行通常搜索。 对于这个问题，显然前两个数有n个，因此我们的dfs使用前两个数作为参数来搜索当前状态有多种情况。 在搜索过程种类中存在很多重复的部分问题，例如在n为5的情况下，存在51351315131511、5315311，这里存在重复的部分问题DFS (3，1 )、对于相同一组参数， dfs 返回值总是相同的，因此
如果不熟悉存储搜索，则导出void类型dfs并将其转换为具有返回值的dfs，最后添加数组记录进行搜索的状态为存储dfs。
void型朴素dfs，代码如下：
defDFS(f，s ) :ifABS ) f-s ) 2: return for i in range(1) 1，n ) :ifIabs ) f-s ) :全局编号=1DFS (s I ) else 3360 return num=0while true : n=int (input () num=0forIinrange(1，n 1 ) :DFS(n，I ) print ) numn ) )
# include bits/stdc.husingnamespacestd； 泰普德夫龙龙LL； ll sum； LDFS(intf，int s ) if (ABS ) f-s )2)返回0； ll num=0； 注意//num必须是函数中定义的局部变量for，而不是全局变量(intI=1； IABS(f-s )； I ) num=DFS(s，I ) 1； /*以上这样的for循环改写如下，代码也是正确的，但是不能直接添加存储数组改写为存储检索。 外部变量sumfor(intI=1； IABS(f-s )； I ) ) num； sum=DFS(s，I )； } */return num； (}int main ) ) { int n； wile((Scanf ) ' %d '，n ) ) { sum=0； for(intI=1； i=n； I ) sum=DFS(n，I )； printf(%lld(n )，sum n )； }返回0； }上述代码dfs函数中的num变量必须在函数中定义ll num=0。 如果全局定义ll num=0，并且在dfs函数中将其更改为num=0，则会出现错误。
每次递归调用函数时，都会生成一个新的函数实例。 这些函数实例具有相同名称的参数和局部变量，但它们是独立的，不会相互干扰。 当进程运行到哪个级别时，该级别的变量将起作用，当返回到上一个级别时，将释放较低级别的同名变量。 这需要深入理解。
记忆化
dfs，添加个dp[f][s]数组记录当前两个数是f和s时有多少种序列，代码如下： #include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 10000;ll dp[1005][1005],sum;ll dfs(int f,int s){ if(dp[f][s]!=-1) return dp[f][s]; if(abs(f-s)<2) return dp[f][s]=0; ll num=0; for(int i=1;i<abs(f-s);i++) num+=dfs(s,i)+1; return dp[f][s]=num; //返回num值前要把num值记录到记忆化数组 //若需取模则改为 return dp[f][s] = num % mod;}int main(){ int n; while(~scanf("%d",&n)){ sum=n; memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++) sum+=dfs(n,i); //若需取模则 sum=(sum+dfs(n,i))%mod; printf("%lldn",sum); } return 0;}下面是对普通搜索和记忆化搜索的dfs函数调用次数进行对比：
（左图为记忆化dfs，右图为朴素dfs，答案均无取模）
至此在时限1s内可计算到n为800，，对于n为1000，还可进一步优化。
④进一步优化
解空间是N的平方（详细为N*N）表格，但是每次都要循环加总，所以成了N的立方，在同样的解空间下，避免循环加总，即可优化到N的平方
重新考虑状态的转移：
如果我们用f(i,j)表示前一个数是i，当前数是1到j的合法序列的个数；有f(i,j) = 1 + f(i,j-1) + f(j,abs(i-j)-1)即分为两个部分1）i作为前一个数，从1到j-1为当前数的合法序列的个数已经计算好，2）求以j为尾数，后面选择1到abs(i-j)-1的合法序列的个数。
如 f(10,5)=f(10,4)+f(5,4);而不是枚举1到5；这样每次解答树只展开两个节点，相当于减少一层循环，虽然解答树的层次还是很深，但是由于记忆的存在，解空间仍然是N的平方。可在100ms内解决。
——摘自https://blog.csdn.net/zhengwei223/article/details/105065435
#include<bits/stdc++.h>typedef long long LL;using namespace std;const int MOD = 10000;int mem[1001][1000];int dfs(int pre, int cur) { if (cur <= 0) return 0; if (mem[pre][cur] != 0) return mem[pre][cur]; return mem[pre][cur] = (1 + dfs(pre, cur - 1) + dfs(cur, abs(pre - cur) - 1)) % MOD;}int main() {int N; cin >> N; cout << dfs(N, N) << endl; return 0;}