K-进制数--线性dp，简单易懂

解题思路:
使用dp[i][0]表示第i为为0时有多少情况，dp[i][1]表示第i为不为0时的情况
参考代码:

#include<bits/stdc++.h>
using namespace std; 
const int N = 25;
int dp[N][5];//使用dp[i][0]表示第i为为0时有多少情况，dp[i][1]表示第i为不为0时的情况 
int n,k;
void solve(){
    cin>>n>>k;
    memset(dp,0,sizeof(dp));
    dp[1][0]=1;//初始化第1为为0有1种情况 
    dp[1][1] = k-1;//初始化第1为不为0有k-1中情况 
    for(int i = 2;i <=n;i++){
        dp[i][0] = dp[i-1][1];//i位为0的情况 = 前一位不为0的情况 
        dp[i][1] = (dp[i-1][0] + dp[i-1][1]) * (k-1);    //i位不为0的情况 = 前一位所有情况 * 本位的(k-1)中情况     
    }
    cout<<dp[n][1];//直接输出第i位不为0的情况数 
}
int main()
{
    solve();
    return 0;
}