更新
似乎根本不可能做到这一点。有人还给我寄了一份不同考试的副本，其中问了几乎相同的问题，但不同之处在于，您不能从任何位置删除，而只能从头或开始删除。很可能这个问题被复制了一个错误。现在我只需要证明这一点并要求重新评估问题考试。
几周前，在数据结构和算法类(class)的考试中，我遇到了以下问题。我无法在给定的时间内解决它，虽然我可能会通过类(class)，但从昨天开始我一直在努力想出一个解决方案，这样我就可以提高我的技能。
问题
给定一个整数 我们反复从任何位置消除一个数字，直到我们只剩下一个数字。函数 PC(n) 被定义为通过所描述的过程可获得的整数平方的最大数目。
例如 PC(32492) = 3 .两种可能的顺序是:
现在设计一个算法，可以在的多项式时间内计算PC(n) d ，其中 d 是 n 中的位数。假设您有一种方法可以在 O(1) 时间内测试一个数字是否为整数的平方。
到目前为止我尝试过的
第一种方法显然是测试每个可能的序列并返回最大值。如果我没记错的话，这是 O(d!)。
改进了蛮力方法，我添加了一个 HashMap，我在其中存储了所有已经计算过的值。这样我们就可以使用 O(1) 查找来避免两次计算相同的值。这显然是实时使用的改进，但我很难获得时间复杂度的下限。所以，据我所知，这不是多项式。
我也尝试了一些贪心算法的方法，但正如预期的那样，我发现每个算法(我能想到的)都没有进行最佳选择。
任何帮助将不胜感激。我尝试在网上寻找类似的问题，但到目前为止还没有运气。
最佳答案
发布此答案，以便问题不会保持开放状态。好像是老师弄错了，不可能。
该问题可能应该只允许消除第一位或最后一位数字，在这种情况下，可以使用动态规划在 O(d^2) 中解决问题。
关于algorithm - 多项式时间内数的平方深度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64719223/