K-进制数-题解（C++代码）动态规划解法

解题思路:

       其实说是动态规划，我觉得这更像一道数学题。

       样例输入给了我们2位数的十进制情况下的答案，90.

       我们不妨从这个地方入手，去求三位数的十进制情况下的答案。由于三位数是从100~999，而我们已经知道了10~99一共有90个满足条件的数字，那么相当于我们知道了110~199中满足条件的个数，即90。而100~109中，共有10个数。很明显100不满足题意，则我们去掉100，那么我们就得到了100~199共有（90+9）个满足条件的数字。那么我们就相当于知道了三位数的十进制情况下的答案。即99*9=891.（因为只要把第一位数进行替换，那么其实情况没什么区别）。

        那么以此类推，我们也能够知道四位数的十进制的答案。下面也来分析一下

        四位数的十进制，也就是1000~9999。由刚刚推导出三位数的步骤来看，我们其实已经知道了1100~1999共有891个满足条件的数字，再由两位数的答案可知，1010~1099共有90个满足条件的数字，而1000~1009由于不满足题意，则不进行计算。也就是说，四位数的十进制情况下共有（891+90）*9=8829。

        那么重点来了，我们可以根据上面的情况列出一个公式来，N位数满足条件的数字=((N-1位数满足条件的数字)+(N-2位数满足条件的数字))*(K-1)

        那么我们可以创建一个数组来储存之前位数的答案，就叫它ans吧。

        ans[0]我们给它填上0，代表着零位数里满足条件的数字为0.

        ans[1]我们给它填上K-1（其实这边没什么理由，只是因为算三位数的时候需要用到而已）

        ans[2]我们给它填上K*(K-1)（其实如果ans[1]=K的话，ans[2]可以通过上面的公式算出来，可是ans[3]就会出错，所以才这样设置初值）

        初值设定好了，我们就可以按照公式进行计算出答案啦！

注意事项:

        其实除了设置初值的地方有些问题，其他的地方都很好理解的。

        第一次写题解，如果写的不好还请多多担待。

参考代码:

#include<iostream>

using namespace std;
int main()
{
	int N, K;
	cin >> N >> K;

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

	cout << ans[N] << endl;
	return 0;
}