第十一章数数难题
尼尔打开了下一题，这个问题很简单，但是却又很复杂。
“恭喜你通过了第一道基础编程，下面进入第二题，阿道夫老师前往办公室的路上，总有许多台阶，他的步子可以一次迈上一块台阶，也可以一次迈过两次台阶。这天，他突然想知道，他有多少种方法，迈上第n阶台阶？“
尼尔在纸上胡乱画了两笔，一看到计数问题，尼尔第一反应是组合数学，可是直接求解第n阶时，繁复的数字完全没有头绪，因为组合数求出来的，有许多无效的路径，根本无法去除，不过想了一会，尼尔忽然灵光一闪，如果把到达第一阶的方法数目记成a1，到达第二阶的方法数目记作a2，那么到达第三阶的方法数目记作a3，那么a3就等于a2+a1!为什么？因为第三阶台阶只可能是从第一阶，迈两步到达，或者是从第二阶，迈一步到达！同理推广到第n阶，那么an=an-1+an-2!那么问题就化归为求解这个递推公式的通项了。
而这让尼尔想起了那个著名的数学公式，斐波那契数列！第一次在教科书上，看到前人用简单的初等数学，便完美的推导出斐波那契数列通项时，尼尔内心是感叹的，他到底是如何联想到这种构造的方法的？灵感么？
（附一个初等数学证明地址，高等数学里面还有差分法的，比较难。
https:wenkubaidu/view/571c93f858f5f61fb6366630htl）
不过，这已经有了现成的结论，那么，便拿来用吧！an=（（1+sqrt（5））n-（1-sqrt（5））n）/sqrt（5），尼尔套用了这个结论，果然，卡牌一时振动，一道apet的意识流反馈了回来，但是，却弹出了一段阿道夫的话。
“作为一个数学家的话，这题是满分，但是如果作为一个魔语者，那么这题还没有入门。这题里面有深意，且往下试试吧。”
这段意识流就如同阿道夫那亲切的声音一样，在耳边响起，随后又变成了评测卡片那机械的意识流
“根据你的回答，进入此题的变形分支系列，阿道夫大师这次，最多一次可以跨越三步，请问，到达第n阶的方式有多少种？n小于10万”
尼尔只是略微思考一番，便得出了结论，an=an-1+an-2+an-3，但是，这已经不是斐波那契数列了，不能再用那套通项公式结论，若是要尼尔再推导一遍这个递推数列的通项结论，可能有些困难。而且尼尔听完阿道夫老师的提醒，心有明悟，自己是在学习魔语，虽然数学可以很好的帮助魔语的实现，但是，运用魔语的才是核心，魔语有什么特性？计算快速！超越人脑反应的速度，那么何不暴力一些呢？推不出，我便直接从第一项开始递推好了！
a［1］=1
a［2］=1
a［3］=2
n=3
while（n≈100000）
{
a[n]=a［n-1］+a［n-2］+a［n-3］;
}
而中括号，代表着魔语的另一重要特性，数组！数组代表着，相同类型的数字，结构体，对象的整齐的排列，你可以通过下标，访问其中的任何一个元素，用在这里刚好合适。
果然，这段魔语很快便运算出了结果，得到了尼尔想要的结果（这里没有考虑位溢出的问题，这些细节忽略吧。）而且也很快速，尼尔略有明悟，隐隐觉得这种方法，是一种魔语者区分于数学家的另一种思维方式，但是短短一两个题目，也没有总结出一个所以然。评测机又响起了阿道夫老师的意识流，尼尔接受到了
“很不错，你一下就想到了。但是，你可能还是处在一种懵懵懂懂的状态中，不急，来看下一个。”
“这次阿道夫大师，终于对楼梯失去了兴趣，来到了尖塔顶层的大厅，数起了砖块！啊，美妙的砖块，这是一个铺有n块砖块的地面，阿道夫大师位于1，1的入口，他想要前往斜对角的n的那块地砖，因为那块地砖下藏着他的宝贝。他每次可以向左走一步，或者向前走一步，那么，请问他有多少种方法，到达藏有宝贝的砖块？”
尼尔脑补出了一块n的坐标系，想象着阿道夫老师在这坐标系上左右腾挪，不免滑稽，楼梯是线性的，而这里是平面的，有些难办。
尼尔开始在脑子里飞速运转，开始对比这两题的相似之处，很显然，这个问题变得更加不同，数列的定义，需要加入新的一纬，但是他们都可以用逆向的思考方式，不考虑这个点能前往那里，只考虑这个点能从哪里来，同理，如果考虑an，的到达方式，那么一定是从下，或者右边来，也就是，an，=an-1，+an，-1，这是一点，而且，为什么要逆向的思考呢？因为递推只能让下标从小的方向往大的方向推，计算到大的状态时，那些小状态就在之前已经计算好了，所以同理，尼尔想好了答案。
a[0][0]=1;
for(ti=0;i≈n;i++)
for（tj=0;j≈n;j++)
{
if(i≈gt;0)
{
a[i][j]+=a[i-1][j];
}
if(j≈gt;0)
{
a[i][j]+=a[i][j-1];
}
}
尼尔用了两重循环，来递推这个公式，并且考虑到，这个地面最边缘的情况时，阿道夫大师是只能从一个方向过去的，比如最右边时，是只能沿着右边边缘往上走的，所以这个格子是不能加上越界的无效数据，这样就递推出了这题的答案，当尼尔通过这道题目的时候，内心隐约起了一些明悟，这时，阿道夫大师预留的总结性意识流流了进来，帮助尼尔对这些知识进行总结。
“这在魔语中，是一种重要的方法。我们把它叫做动态规划，动态规划的本质，是对问题状态的定义和状态转移方程的定义。并且这个状态可以由更小的状态转移过来，那么我只要知道了最小解的初始状态，就可以一步步的推演，变成最终要求解的目标解，比如前几个问题里，定义下走到第n阶的方法数为一个状态，而这个状态可以由第n-1阶的解加上第n-2阶的解得到。这是与数学不同的。”
尼尔感觉心里那些朦胧的感觉一下被戳破了。脑子里忽然闪现出一片朦胧的场景。那是神创世的那个梦境，梦境的天空里，有一行行的文字
启动世界
设置宇宙初始参数
定义转移方程中e=c2
世界推演中
&/div>
------------------------------------------