K-进制数 （Java代码）

n代表几位数，k代表几进制，sum[n]表示n位k-进制数总数。
要保证没有连续的0，
以 k=10为例
当n=1,sum[1]=k-1; 9
当n=2,sum[2]=(k-1)*k;k-1表示十位的可能情况数,k表示个位可能情况数。90
当n=3,sum[3]=(k-1)*(sum[2]+sum[1])  891
规律 sum[n]=(k-1)*(sum[n-1]+sum[n-2])
规律的得出我没办法用语言表达（只可意会，不可言传）
也可以用递归写。
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();// 位数
		int k = sc.nextInt();// 进制
		int[] sum = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			if (i == 1)
				sum[i] = k - 1;
			else if (i == 2)
				sum[i] = k * (k - 1);
			else
				sum[i] = (sum[i - 1] + sum[i - 2]) * (k - 1);
		}
		System.out.print(sum[n]);
	}
}