K好数--算法复杂度分析求指点
问题描述如果一个自然数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和L的数据规模都是100,那么我现在考虑的有两个解法。一种是回溯法,一位一位的遍历每一种情况。如果是K进制,L位的话,那么总共要遍历K的L次方种情况。毕竟每一位上都可以是0到
K-1,当然回溯到不合题意的情况。
第二种是动态规划。求L位K进制数中K好数的数目,可以先求出L-1位K好数,L-2位K好数......1位K好数。设F[i][j]表示i位以数字j结尾的K好数数目,1<=i<=L,0<=j<K,状态转移方程:
F[i][j] = F[i-1][p](p遍历0到k-1的情况)的总和。那么这个算法的复杂度也是K的L次方次加法。
那么问题来了~~动态规划的节约时间的优点体现在哪里呢?或者说我用回溯法会时间超时,动态规划却不会的原因在哪里呢?
不知道我有么有清楚的描述我的问题~~~~求指点