蓝桥杯算法训练（三） K好数（动态规划） C语言

蔚落 2022-03-20 17:56 324阅读 0赞

# K好数 C语言 #

**问题描述**

如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

**输入格式**

输入包含两个正整数，K和L。  
输出格式  
输出一个整数，表示答案对1000000007取模后的值。

**样例输入**  
4 2

**样例输出**  
7

**数据规模与约定**

对于30%的数据，KL <= 106；

对于50%的数据，K <= 16， L <= 10；

对于100%的数据，1 <= K,L <= 100。

这道题是一个比较简单的**动态规划法**的应用（笔者也就是没写完了才这么说，事实上没少被折腾T\_T）

动态规划的基本思路：  
1、研究问题的部分解，产生递推式  
2、找到初始值  
3、填表——根据初始值和递推关系，填写问题的所有部分解

所以呢，在这道题上，我们要先找**递推关系**：

1、首先，我们先假设 **k==4**，就是数字是个四进制，那么每一位数能取的值自然就只有0,1,2,3。

2、当 **L==1**时，即数字只有1位数，K好数是0,1,2,3四个。

3、当**L==2**时，数字有两位数，当我们确定了第一位数后，第二位数只要与第一位数不相邻就行了。

eg：若第一位数取1，第二位数只能取 1 和 3，则**位数 L==2，以 1 开头的K好数有2个，11 和 13。**

同理，第一位数取3，第二位数只能取 0 、1、3，即**位数L==2，以3开头的K好数有3个，30、31、33。**

（前面的eg很重要，请认真阅读）

4、当**L==3**呢？，我们还是确定第一位数，假如第一位数等于 1，那么第二位数只能取 1 和 3，且后面两位必须互不相邻，**即是一个两位的，以1或3作为第一个数的K好数。**

所以我们可以得知，第一位数是1的三位K好数的数量等于第一位是1 和 3的两位K好数的数量的和！

其他同理，于是有下面这张表：  
![在这里插入图片描述][20190214122731279.png]注：i 指的是位数， j 指的是以 j 作为第一位数，表中数据指的是对应的K好数的数量。

所以我们需要申请一个二位数组 dp\[ i \] \[ j \] 用来存放K好数的数量。

需要注意的是，当L==1时可以用 0 作为第一位数，但是当 L>2时，0不能作为第一位数。

以下是系统认可的正确代码：

#include <stdio.h>
    
    #define MOD 1000000007 
    
    int main() { 
    	long long k,l,sum=0,i,j,z;
    	long long dp[500][105];		//dp[i][j]用来存放符合条件的 k好数的数量, i代表数字有多少位，j代表以 j数作为第一位 
    	
    	scanf("%lld%lld",&k,&l);	//k:进制，l:位数 
    	
    	for(i=0;i<k;i++)
    		dp[1][i]=1; 	//作为动态规划的初始值，当l==1时， 每个数都是 k好数，且以 i作为第一位的只有1个（i）。
    		
    	if(l>=2)
    	{ 
    		for(i=2;i<=l;i++)  
    			for(j=0;j<k;j++)
    				for(z=0;z<k;z++)
    				{ 
    					if(z!=j+1 && z!=j-1) //左右不相邻 
    					{ 
    						dp[i][j] += dp[i-1][z]; 
    						dp[i][j] %= MOD;
    					}
    				}
    	} 
    	
    	for(j=1;j<k;j++)
    	{ 
    		sum += dp[l][j];
    		sum %= MOD;
    	}	//算出 l位数中 K好数的数量，即最终结果
    	
    	printf("%I64d",sum);
    	  
    	return 0;
    }

事实上这段代码直接省略了所有以 0 做为第一个数字的情况，所以当输入4 1、时，结果为3。（笔者认为正确答案是4个K好数,分别为0,1,2,3）。

但是，但我将改进后的代码放进系统评测却只给了我90分，代码如下：

#include <stdio.h>
    
    #define MOD 1000000007 
    
    int main() { 
    	long long k,l,sum=0,i,j,z;
    	long long dp[500][105];		//dp[i][j]用来存放符合条件的 k好数的数量, i代表数字有多少位，j代表以 j数作为第一位 
    	
    	scanf("%lld%lld",&k,&l);	//k:进制，l:位数 
    	
    	for(i=0;i<k;i++)
    		dp[1][i]=1; 	//作为动态规划的初始值，当l==1时， 每个数都是 k好数，且以 i作为第一位的只有1个（i）。
    		
    	if(l>=2)
    	{ 
    		for(i=2;i<=l;i++)  
    			for(j=0;j<k;j++)
    				for(z=0;z<k;z++)
    				{ 
    					if(z!=j+1 && z!=j-1) //左右不相邻 
    					{ 
    						dp[i][j] += dp[i-1][z]; 
    						dp[i][j] %= MOD;
    					}
    				}
    	} 
    	
    	if(l==1)	//如果位数等于1,0可以作为第一位数，K好数的数量刚好等于K值 
    	{ 
    		sum=k；
    	} 
    	else	//如果l!=1, 0不能作为第一位数 
    	{ 
    		for(j=1;j<k;j++)
    		{ 
    		sum += dp[l][j];
    		sum %= MOD;
    		}	//算出 l位数中 K好数的数量，即最终结果
    	} 
    	
    	printf("%I64d",sum);
    	  
    	return 0;
    }

系统显示，错误的是当输入为1 1 时，输出为0，而不是正确答案1。但我在自己的电脑上运行，输入1 1，结果确实为1，代码逻辑也没有问题。

所以我相当无语…

好了，这道题就这样，看不懂的读者欢迎下方提问，笔者为了讲清自己的思路，硬是写了好几版文章（写了后觉得讲得不好重新推掉重写…T\_T）最后直接用举个栗子的方法来表达自己的思路，希望读者能看懂，写得不好的话，还请见谅。

另外，我更加深刻地认识到：**表达自己的思路真的不如举个栗子来得简单粗暴，清晰明了！！！**

[20190214122731279.png]: /images/20220320/5f8a3147cc184e1596bf26371aeeafe9.png