试题 算法训练 K好数

资源限制

时间限制：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%的数据，KL <= 106；

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

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

---

 

PART 1

看到题目首先想到的就是用递归来解决问题。然后奉上递归做出的答案。：

递归方法：

 1 import java.util.Scanner;
 2 
 3 public class Main{
 4     private static int l, k;
 5     private static long value;
 6     //private static int[] num;
 7     public static void main(String args[]) {
 8         Scanner scan = new Scanner(System.in);
 9         k = scan.nextInt();
10         l = scan.nextInt();
11         scan.close();
12         value = 0;
13         int[] num = new int[l];
14         int index = 0;
15         f(index, num);
16         System.out.println(value%1000000007);
17     }
18     
19     private static void f(int index, int[] num) {
20         // TODO Auto-generated method stub
21         if(index == l) {
22             if(panduan(num)) {
23                 value++;
24             }
25             return;
26         }
27         for(int i = 0; i < k; i++) {
28             if(i == 0 && index == 0) continue;
29             num[index] = i;
30             f(index+1, num);
31         }
32     }
33     private static boolean panduan(int[] num) {
34         // TODO Auto-generated method stub
35         for(int i = 0; i < l - 1; i++) {
36             if(num[i] - num[i+1] == 1 || num[i+1] - num[i] == 1)
37                 return false;
38         }
39         return true;
40     }
41 }

View Code

 

结果提交之后只有30分，运行超时。

然后思考很久后想起来了动态规划的方法。但是在课堂上学的动态规划，这时候只能想起来它是通过把一个大问题分解成若干个具体的小问题，一层一层的解决。但是具体的怎么实现，具体的思路啥的全忘了，只能再次求助伟大的网友。

发现了一篇非常全面，完美的讲解动态规划的文章。（从中彻底的搞懂了啥叫动态规划）

链接奉上：教你彻底学会动态规划——入门篇