超越学姐爱字符串

超越学姐爱字符串

链接：
来源：牛客网

超越学姐非常喜欢自己的名字，以至于英文字母她只喜欢“c”和“y”。因此超越学姐喜欢只含有“c”和“y”的字符串，且字符串中不能出现两个连续的“c”。请你求出有多少种长度为n的字符串是超越学姐喜欢的字符串。答案对1e9+7取模

思路：dp
d p [ i ] [ 0 ] dp[i][0] dp[i][0]：第i个位置放字符c
d p [ i ] [ 1 ] dp[i][1] dp[i][1]：第i个位置放字符y

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
#define mod 1000000007
typedef long long ll;
ll dp[maxn][2];
int main(){int n; scanf("%d",&n);dp[1][0]=dp[1][1]=1;for(int i=2;i<=n;i++){dp[i][0]=dp[i-1][1]%mod;dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod;}printf("%lldn",(dp[n][0]+dp[n][1])%mod);return 0;
}