K-进制数 递归算法，10行C++代码，满分解决

解题思路:
    假设K=10，first0(1)表示当N为1，最高位为0时满足条件的数量，first1(1)表示N为1，最高位不为0（即1~K-1）时满足条件的数量：

    1、当N=1时，first0(1)=1，first1(1)=K-1=9。

    2、当N=2时，相当于说在前面N=1的基础上新增了一位数。

            对于first0(2)，共2位数，最高位固定为0，剩下N-1=1位，而我们在上面讨论过1位数的情况，所以first0(2)=1*first1(1)=first(1)=9;

            对于first1(2),最高位有K-1=9种情况，第二位可以为0也可以不为0，因此first1(2)=（first0(1)+first1(1))*(K-1)=(1+9)*9=90;

    3、当N=3时，相当于在N=2的基础上新增了一位，

         同理，first0(3)=1*first0(2)=9;

                   first1(3)=(first0(2)+first1(2))*(K-1)=(9+90)*9=891;  

        结论：根据推到可知

            first1(N)=(first1(N-1)+first0(N-1))*(K-1)

            first0(N)=first1(N-1)

            故结合上面两个式子可得：first1(N)=(first1(N-1)+first1(N-2))*(K-1);

             当N=1时，first1(1)=1;

注意事项:

    为了保证递归顺利完成，假设N=0时，first1(0)=1！！

参考代码:

#include<bits/stdc++.h>
using namespace std;
long result(int n,int k){
	if(n==0){
		return 1;
	}
	if(n==1){
		return k-1;
	}
	return (result(n-1,k)+result(n-2,k))*(k-1);
}
int main(){
	int N,K;
	cin>>N>>K;
	cout<<result(N,K);
	return 0;
}

    对于此程序还可以考虑用空间换时间来进一步优化，即增加全局的记忆数组array，元素array[n]保存result(n,k)的值，递归过程中先判断数组中有没有值，如果有则直接用，如果没有则递归计算！！！