「水经验」CF1339A Filling Diamonds

审题解的说是重复解法。我寻思着就算题简单到爆炸这也不是重复解法啊？我想要审题解的人给一个解释。 经验还是要水的。这里说一个比较直观的转移。 设 $f(n)$ 为 $n$ 时的方案数。 考虑 $n$ 每次 $+1$，可以拆成两个单独的小菱形加上 $n-1$ 的方案，那么看上去通过分类讨论在左边插入还是右边插入，答案应该为 $$ f(n)=2\cdot f(n-1) $$ 但是这并不对，因为两种方式会有重复。发现重复就重复在共同使用了中间那个大小为 $n-2$ 的多边形上。于是可以知道正确的递推应该是 $$ f(n)=2\cdot f(n-1)-f(n-2) $$ 归纳可得 $$ f(n)=2\cdot (n-1)-(n-2)=n $$