问题描述
如果一个自然数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。
题目解析：
自己也遇到了好几次动态规划的题目，做下来发现基本是大事化小，小事就简单了
首先解释一下k好数是什么意思，就是说在一个数在k进制下，任意两位数字不是相邻的数，比如10就不是k好数，因为1和0相邻，接下来就是l位数，这是一个坑，一开始我以为是在10进制下有多少位，之后才发现其实是在k进制下有多少位，这个会造成很大的差别，比如说10进制下的两位数与在4进制下的两位数，数的区间 存在着很大的差异，10进制的两位数就是10-99，而4进制下的两位数就是10-33，而且这之间的数也是不同的。解释完k好数是什么概念，接下来就好办了。
方法一
按部就班解题，这种方法能做出来，但是时间复杂度太高，不能AC,不建议使用，首先就是根据l位数，确定范围，比如说2位数，那么范围就固定在了10-33之间，之后通过将10和33转换成10进制下的数即4和15，这样就找到了数据段的区间，之后按照for循环一次检查，首先将对应的数转换成k进制下的数，然后进行判断，如果则+1，否则不动
import java.util.Scanner; public class Main { public static int change10(int n,int k)//将k进制的数重新转换成10进制的数 { int k1=1; int sum=0; String str1=String.valueOf(n); for(int i=0;i<str1.length();i++) { sum+=n%10*k1; n/=10; k1*=k; } return sum; } public static String changek(int n,int k)//将一个数转换成k进制 { String str1=""; while(n>=k) { str1+=String.valueOf(n%k); n=n/k; } str1+=String.valueOf(n); return str1; } public static boolean panduan(String str1) { boolean result=true; char []ch1=str1.toCharArray(); for(int i=0;i<ch1.length-1;i++) { if(Integer.parseInt(String.valueOf(ch1[i]))-Integer.parseInt(String.valueOf(ch1[i+1]))==1|| Integer.parseInt(String.valueOf(ch1[i]))-Integer.parseInt(String.valueOf(ch1[i+1]))==-1) { result=false; break; } } return result; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int k=sc.nextInt();//k进制 int l=sc.nextInt();//l位数 int k1=1; int count=0; int start=1; int end=0; if(l==1) start=0; else { for(int i=0;i<l-1;i++) start*=10; } start=change10(start, k);//找到最起始的位置 //System.out.println(start); for(int i=0;i<l;i++) { end+=(k-1)*k1; k1*=10; } end=change10(end, k);//找到最末端的位置 //System.out.println(end); for(int i=start;i<end+1;i++) { String n=changek(i, k);//将区间范围内的数都转换成k进制下的数来比较 if(panduan(n)) { //System.out.println(n); count++; } } System.out.println(count%1000000007); } }
方法二
使用动态规划进行求解
用动态规划进行求解，就需要找准以什么来进行来作为类似于递推的公式，这里通过划分开头的数来进行，
定义一个数组dp[l][k];
dp[i][j]表示的是i位数首个数字为j的所有情况，这时候我们来分析，dp[i][j]就是在所有的dp[i-1][j]上面重新添加了一位数，但是添加的数又不是随便的，必须要满足一个条件就是添加的数不能是相邻的数所以dp[i][j]+=dp[i-1][x],，x表示的就是所有不是j相邻的数，所以可以得出递推公式了
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int k=sc.nextInt(); int l=sc.nextInt(); int [][]dp=new int [l][k]; for(int i=0;i<l;i++) { for(int j=0;j<k;j++) dp[i][j]=0; } for(int i=0;i<k;i++) dp[0][i]=1; for(int i=2;i<l;i++) { for(int j=0;j<k;j++) { for(int x=0;x<k;x++) { if(x-j!=1&&x-j!=-1) { dp[i][j]+=dp[i-1][x]; dp[i][j]%=1000000007; } } } } int sum=0; for(int i=1;i<k;i++) { sum+=dp[l-1][i]; sum%=1000000007; } System.out.println(sum); } }
作者很菜，如果说的不对，请指教
