题目

【资源限制】 时间限制：1.0s 内存限制：256.0MB

【问题描述】 如果一个自然数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%的数据，K L <= 106；

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

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

题目分析与理解

解题方法：动态规划

dp[i][j]=dp[i][j]+dp[i-1][k]

这里的动态规划是创建数组记录每一次的最优解，最后达到整体的最优解。

K好数举个例子，3位10进制（L位K进制）：

在K好数的题目中，相邻两个数位的数字不能相邻： 首先分析个位数（第1位数10进制数），可以0-9取值，每个数字都可以取一遍，创建一个二维数组dp，第一行记录每一个数字都可以取一遍：

01234567891111111111

然后分析十位数（第2位数10进制数），取值也是0-9，但是十位每取一个值，个位都不能相邻，例如十位取0，个位只能取0或2-9共8个数字，二维数组dp在第1行的基础上把可取的结果相加：

012345678911111111119888888889

然后分析百位数（第3位数10进制数），取值也是0-9，但是百位每取一个值，十位都不能相邻，例如百位取1（注意百位不能取0，也就是说首位不为0），十位只能取1或3-9共8个数字，二维数组dp在第2行的基础上把可取的结果相加：

012345678911111111119888888889跳过656666666666666574

最后把dp二维数组最后一行相加，得到600，即为3位10进制K好数的最终结果。

在解题过程中参考了很多文章理解动态规划，比如：

参考了该博主的文章：https://blog.csdn.net/qq_41714549/article/details/87435089

（这位博主文章中“排除首位为0”部分的代码是错的）

同时还参考了这位博主的文章：https://blog.csdn.net/libin56842/article/details/19910663

（在这个博主的文章中看到dp[i][j]的意思：dp[i][j],其中i代表的是数字有几位，j代表首位放j的情况有几种）

附上c++代码

#include <iostream> #include <cmath> using namespace std; #define MOD 1000000007 //L位K进制 void Count(int length,int range){ long long int dp[110][110],sum=0; //dp[i][j]：这个数有i位，首位放j的情况 ,longlong：避免int溢出 for(int j=0;j<100;j++) dp[0][j]=1; for(int i=1;i<length;i++){ for(int j=0;j<range;j++){ for(int k=0;k<range;k++){ if(abs(j-k)!=1){ if(i==length-1 && j==0) //当i为数的最高位时不能为0 continue; dp[i][j]=dp[i][j]+dp[i-1][k]; dp[i][j]%=MOD; } } } } for(int i=0;i<range;i++){ sum+=dp[length-1][i]; sum%=MOD; } cout<<sum; } int main(int argc, char** argv) { int k,l; cin>>k>>l; //题目先输入k再输入l if(k==1 && l==1) cout<<0; else if(k>1 && l==1) cout<<k; else if(l>1) Count(l,k); return 0; }

再附上运行结果

（其他博主关于K好数的的文章已经写的很好了，写这篇文章的目的主要是为了巩固刚学的动态规划）