动态规划法——K-进制数

解题思路:

对于一个k进制数：数码为0~k-1，设从右到左依次为第0,1,2，……，n-1位，可以分别讨论第i位是否为0的不同情况：

1. 若第i位为0，则第i-1位不能为0；

2. 若第i位不为0，则第i-1位任意；

如果用一个二维数组表示所得结果，我们不妨用a[i][0]表示第i位为0的情况数，用a[i][1]表示第i位不为0的情况数。

            a[0][0] = 1; a[0][1]= k-1;
            //进行初始化，设置初始状态

根据以上分析，可以得到下面代码（状态转移方程）：

             a[i][0] = a[i-1][1];
        //第i位为0,则第i-1位不为0
        a[i][1] = (a[i-1][0] + a[i-1][1]) * (k-1);

注意事项:
最高位不为0，因此最后的输出结果是a[n-1][1].
参考代码:

#include <stdio.h>
 
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int a[n][2];
    a[0][0] = 1; a[0][1]= k-1;
    for(int i = 1; i < n; i++){
        a[i][0] = a[i-1][1];
        //第i位为0,则第i-1位不为0
        a[i][1] = (a[i-1][0] + a[i-1][1]) * (k-1);
    }
    printf("%d",a[n-1][1]);//最高位不为0
    return 0;
}