Question 输入n，符合要求的序列为：第一个数为n，第二个数不大于n，从第三个数起小于前两个数的差的绝对值，后面以此类推。求有多少种序列？答案取模10000（数据：n最大为1000）

Sample input：4 / output：7 input：5 / output：14 input：6 / output：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因为是递归所以从上往下算。

记忆化搜索：

1. 递归函数的结果以返回值形式存在，不能以全局变量或参数形式传递。
2. 不依赖任何外部变量。 （根据以上两个要求把朴素暴搜dfs写出来后，添加个记忆化数组就ok了）
3. 记忆化数组一般初始化为-1。在每一状态搜索的开始进行判断，如果该状态已经计算过，则直接返回答案，否则正常搜索。

对于这道题，很明显前2个数共有n种情况，所以我们的dfs以前2个数为参数，搜当前状态有几种情况。可以发现，搜索过程种存在很多重叠子问题，比如n为5时，5 1 3→5 1 3 1→5 1 3 1 1，5 3 1→5 3 1 1，这里便存在重叠的子问题dfs(3,1)，对于相同一组参数, dfs 返回值总是相同的 ，所以在前面已求出dfs(3,1)结果后把答案存储到记忆数组dp[3][1]中，后面再遇到直接调用记忆数组就可以了。

如果对记忆化搜索不熟练，可以先写出void型dfs，再转化为有返回值的dfs，最后再加个数组记录已经搜过的状态就是记忆化dfs了。

①void型朴素dfs，代码如下：

②改成“无需外部变量”的有返回值的朴素dfs，代码如下：

上述代码dfs函数内的num变量必须在函数内定义ll num=0。如果是在全局定义ll num=0，dfs函数内改为num=0，则是错误的。

每递归调用一次函数，系统就会生成一个新的函数实例。这些函数实例有同名的参数和局部变量，但各自独立，互不干扰。流程执行到哪一层，那一层的变量就起作用，返回上一层，就释放掉低层的同名变量。这个需要深刻理解一下。

③记忆化dfs，添加个dp[f][s]数组记录当前两个数是f和s时有多少种序列，代码如下：

下面是对普通搜索和记忆化搜索的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