递推思想就是把这一项递推到前一项，把问题简单化，例如Fibonacci数列f(n)=f(n-1)+f(n-2)
题目的意思就是n个长度字符中至少有3个连续的U的字符有几种
于是问题核心就是怎么递推，使问题规模减少
假设答案为f(n)，从第一个连续的U开始编号为第i,i+1,i+2个
于是字符串可以分为3部分:
第一部分为1~i-1
设有g(i-1)种
g(i-1)=全排列2^(i-1) - 存在3个U的情况f(i-1)
第二部分为3个U
只有一种
第三部分为i+3~n
有2^(n-i-2)种
利用乘法原则上述乘起来就是答案为f(n)=∑g(i-1)*2^(n-i-2) i∈[1，n-2] ，其中g(i-1)=2^(i-1) - f(i-1)
但是有一个问题，我们假设的是第一个连续的U开始编号为第i,i+1,i+2个，但是g(i-1)中却包含了第i-1也是U的种类
那么会导致与定义不符
于是分为两种情况
1）第i-1位为L，此时f(n)=∑g(i-2)*2^(n-i-2) i∈[2，n-2] ，其中g(i-2)=2^(i-2) - f(i-2)
2）第i-1位不为L，也即是不存在i-1位置，i=1，此时f(n)=2^(n-3)
依据加法原则得f(n)=2^(n-3)+∑g(i-2)*2^(n-i-2) i∈[2，n-2]
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int f[35],g[35];
int solve(int n)
{if(n<3) return 0;else if(f[n]) return f[n];else{int ans=0;for(int i=2;i<=n-2;i++){if(!g[i-2]) g[i-2]=(1<<(i-2))-solve(i-2);ans+=g[i-2]*(1<<(n-i-2));}ans+=(1<<(n-3));return f[n]=ans;}
}
int main()
{f[0]=f[1]=f[2]=0;f[3]=1;g[0]=0;g[1]=2;g[2]=4;
// for(int i=4;i<=30;i++) if(!f[i]) solve(i);for(int n=4;n<=30;n++){int sum=0;for(int i=2;i<=n-2;i++){if(!g[i-2]) g[i-2]=(1<<(i-2))-f[i-2];sum+=g[i-2]*(1<<(n-i-2));}f[n]=(1<<(n-3))+sum;}int N;while(scanf("%d",&N)&&N)printf("%d\n",f[N]);return 0;
}