K-进制数-递推与动态规划思想（C语言代码）

解题思路:

把题看成组合类题目,N表示位数,k是进制.根据题意可知,首位有k-1种选择(首位不为0),其余位不考虑两个0相临的情况下每位都有k种选择

 列如:N=3,k=10;其中首位有9种选择(首位不为0),其余位不考虑两个0相临的情况下每位都有10种选择;

所以我们可以把除首位的其余位的组合求出,再乘以首位的选择数就是结果,接下来就是求除首位外的其余位的组合数,运用递推和dp的思想:分析最后一位只有可能是2种情况,以0结尾或者以非0结尾,所以将一个大问题分解成了两个小问题;

其一:以0结尾的情况,其前面一位一定为非0结尾,一定为非0结尾又是刚刚提到的子问题;

其二:以非0结尾的情况,其前面一位可为0可为非0,前一位以0或者非0结尾又是一个子问题;

所以,我们可以设dp[i][0]表示以0结尾的i位数的所有合法选择,dp[i][1]表示以非0结尾的i位数的所以合法选择,dp[i][2]表示以非0或以0结尾的i位数的所以合法选择;

通过刚刚的分析,可以得到dp[i][2] = dp[i][0] + dp[i][1];    dp[i][0] = dp[i-1][1];    dp[i][1] = (k-1)*dp[i-1][2];


参考代码:

#include <stdio.h>
#include <string.h>
int dp[100][3];
int main()
{
    int wei,k,i;
    while(scanf("%d%d",&wei,&k)==2)
    {
        memset(dp,0,sizeof(dp));
        dp[1][1] = k-1;
        dp[1][2] = k;
        dp[1][0] = 1;
        for(i=2;i<=wei-1;i++)
        {
            dp[i][0] = dp[i-1][1];
            dp[i][1] = (k-1)*dp[i-1][2];
            dp[i][2] = dp[i][0]+dp[i][1];
        }
        printf("%d\n",(k-1)*dp[wei-1][2]);

    }
    return 0;
}