Question

c++编程问题 回溯算法 请大师帮忙讲解 源代码不要 上课没听懂啊！！

描述 Description
仅由0和1组成的长度为n字符串，其中不可含有三个连续的相同子串。求这样的字符串的个数。

输入格式 Input Format
字符串长度n（n<=30）。

输出格式 Output Format
所有满足条件的字符串的个数。

样例输入 Sample Input
2

样例输出 Sample Output
4

Answer 1

//这题不可用回溯法来解的,因为枚举的空间太大了,有2^30次方呢,这样会挂掉的,应该用DP
//dp[i][j][k]表示的是长度为i的串,以j,k为末尾两位的合法串有多少种. 长度i+1可以从i的加上0或者加上1得到
//dp[i+1][k][p]=sum{dp[i][j][k]}(j!=p&&k!=p)

#include<malloc.h>
#include<stdio.h>
int dp[33][2][2]={0};
int main()
{
int i,j,k,p,n;
dp[1][0][0]=1;
dp[1][0][1]=1;
dp[2][0][0]=1;
dp[2][0][1]=1;
dp[2][1][0]=1;
dp[2][1][1]=1;
for(i=3;i<33;i++)
{
for(j=0;j<2;j++)
{
for(k=0;k<2;k++)
{
for(p=0;p<2;p++)
{
if(j==k&&k==p)continue;
dp[i][k][p]+=dp[i-1][j][k];
}
}
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1]);
}
return 0;
}

Answer 2

afdasf

Answer 3

这个你去你问你老师吧，一句两句说不清楚的