这道题是一道递推的题目，但同时和动态规划有着一定的相似性，之所以来写这道题的题解是因为第859.【TYVJ1449】猫咪的进化一题可以用到这种思想

【算法分析】

方法一、排列组合（但需要运用动态规划）

   可以列出公式，在n个格子中放x个3（其中x为偶数，包括0）。

   c(n,x)\*9^(n-x)-c(n-1,x)\*9^(n-x-1)含义为在n个格子中取x个3，且不考虑第一位的特殊情况为c(n,x)\*9^(n-x),而第一位为0的情况为c(n-1,x)\*9^(n-x-x)，两者相减，就为答案。

   方法二、递推

   考虑这种题目，一般来说都是从第i-1为推导第i位，且当前位是取偶数还是去奇数的。

   恍然大悟，可以用f[i][0]表示前i为取偶数个3有几种情况，f[i][1]表示前i位去奇数个3有几种情况。

   则状态转移方程可以表示为：

   f[i][0]=(f[i-1][0]*x+f[i-1][1])

   f[i][1]=(f[i-1][1]*x+f[i-1][0])

   边界条件：f[1][1]=1；f[1][0]=9

最重要的是状态转移方程，其实这里写“状态转移方程”就是因为本质上和动态规划是类似的，需要注意的是这种写法f[i][0]和f[i][1]同时递推/DP，可能是某些看似不可解的题目的关键点

这就是本题的解析，代码就不贴了哈