递推（经典例题）

递推例题 在这之前，我们先了解一下递推的基本原理

举一个生活中的例子：

你要上楼梯（每层楼有20个台阶，1楼没有架空）

你想上到3楼，你要从1-2-3这个顺序爬到3楼

你从1到2，再从2到3

换句话说，你走到第2楼是在你身处第1楼的情况下才能有的，走到第3楼是你在你身处第2楼的情况下才有的

这样就可以得到一个十分简单的递推式：f(i)代表你走到第i楼所走的台阶数，一共要走n楼

f(i)=f(i-1)+20, 1≤i≤n

一般的递推包含3个部分

1、分析出递推式

2、确定变量范围

3、初始化 ——————————————————————————————— 题目描述 用1 x 1和2 x 2的地砖不重叠地铺满N x 3的地板，共有多少种方案？ 输入 一个数字N h[i]=h[i-1]*10; f[i]=f[i-1]*9+(h[i-1]-f[i-1]); f[i]%=12345; h[i]%=12345; }

第四题：

题目描述 圆周上有N个点。连接任意多条（可能是0条）不相交的弦（共用端点也算相交）共有多少种方案？

输入 读入一个数N。1 f[i]+=f[j]*f[uck]; f[i]%=12345; uck++; } }

第五题： 题目描述 在网格中取一个N x 1的矩形，并把它当作一个无向图。这个图有2(N+1)个顶点，有3(N-1)+4条边。这个图有多少个生成树？答案 mod 12345 后输出。

输入 样例输入：1

输出 答案 mod 12345 后输出。

样例输入 1

样例输出 4