找到第n个count-and-say序列元素

Question

Given a problem, the count-and-say sequence is the sequence of integers beginning as     follows:
1, 11, 21, 1211, 111221, ...

读出1作为"1"或11读出11作为"两个1"或21读出21作为"一个2,然后一个1"或1211.给定整数n,产生第n个序列.

我通过扫描每个字符串并相应地生成下一个字符串来制定解决方案需要时间为O(nm)其中m是最大字符串的长度,n是给定的数字

这是代码

void countnsay(char str[][1000],int n)
{
int i=1,k;
int j=0;
while(i<=(n-1))
{
//scan str[i-1]
j=0;
k=0;        //for building the new string array 
while(j<strlen(str[i-1]) )
    {
    char c=str[i-1][j];
    int cnt=1;

    while(c==str[i-1][++j])
    cnt++;

    str[i][k++]=cnt+48;
    str[i][k++]=c;

    }
str[i][k]='\0';
i++;

}
printf("%s",str[n-1]);  
}




int main()
{
int n=5;
char str[1000][1000];
strcpy(str[0],"1");
countnsay(str,n);
return 0;
}

有没有更好的解决方案来解决这个问题？请提供一些建议/提示.Thanx提前

Answer 1

您可以使用动态编程.一段时间后,您将遇到已经计算过的已存在的子串.您可以保留已计算序列的映射:

1 -> 11
11 -> 21

现在你需要计算1211.

你首先去1,你已经知道了11.

你遇到了2.你没有这个,所以计算12并将其添加到地图:

2 -> 12

你遇到的11,再次,你在你的地图中有21.

连接这些,你得到

111221

和新地图

1 -> 11
11 -> 21
2 -> 12

编辑:您只查找连续相同的数字,所以只保留在地图中.