【编程问题】猜数字游戏

空间限制:32768K

这个问题比较难。

首先，采用动态规划的思想

首先我们分析dp[i]表示前I个数的合法个数。

当第I个数是质数时，除了1，什么都不能除，所以可以随意选择Y或N，所以dp[i] = dp[i-1]。

当第I个数不是素数的幂时，比如610，那么他们的情况实际上是由前面的数决定的。对于6，如果2，3是YY，那么6一定是Y，其他情况6一定是N，所以dp[i] = dp[i-1]。

当第I个数是一个素数的幂，即2，4，8，16时，情况就复杂了。假设现在有2个，4个，8个，那么有多少种情况？仔细分析也能找到规律。

YYY，YNN，NNN，YYN在这四种情况下。

对于2，4

Yn，YY和NN。

我们发现其实是有规律的，首先你可以或者不可以两者兼得，然后你从左到右加y:

YNN，YYN .

所以在这种情况下，我们得到这样的规律:如果有n次方，则在n+1中存在可行的情况。

经过分析，我们可以得到计算方法。对于12:

2，4，8这三个数字是幂，有四种可能。

3和9的幂有三种可能。

5，7，11，分别是两种可能。

其他数字由其他数字决定。

所以最终结果是4 3 2 2 2。

所以当我们思考这个问题的时候，我们最终变成了寻找质数和质幂的个数。

？