K-进制数的dp求解

解题思路:在看了一些其他同学的递归解法后，想到了是否可以用dp来求解（下面有一些说法是借鉴的其他同学的），首先我们假设1代表该数位不是0，可以是1~k-1的任意一个数，0就代表零，-1代表任意（可以是零也可以是1），那么最高位数必定是1，后面的第二位数可以为1，也可以为0，当第二位数位1，则后面又可以是1或0，当第二位数位0，那么后面的数必定为1，根据这个思路，写出dp[i][j]的意义，一个i位数且最高位为j的有效K-进制数的总数，这里的j可以简化为2，

dp[i][0],就是当前位为0，dp[i][1]就是当前位为1（1~k-1）

dp[i][0] = dp[i - 1][1] ;

dp[i][1] = (dp[i - 1][1] + dp[i - 1][0]) * (k - 1)
注意事项:
dp[1][0] = 1,一位数且是0为一种

dp[1][1] = k - 1
参考代码:

#include<iostream>
using namespace std;

int main() {
	long long  N, K, dp[20][2];     // 位数  进制  N+K<=18
	cin >> N >> K;	
	dp[1][0] = 1;
	dp[1][1] = K - 1;

	for (int i = 2; i <= N; i++) {
		dp[i][0] = dp[i - 1][1];
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (K - 1);
	}

	cout << dp[N][1] << endl;
	return 0;
}