多项式时间内数字的平方深度
Square depth of number in polynomial time
更新
看来根本不可能做到这一点。有人还给我发了一份不同的考试副本，其中提出了几乎相同的问题，但不同之处在于，你不能从任何位置移除，而只能从开头或开始移除。问题很可能是在复制时出现错误。现在我只需要证明这一点，并要求重新评估问题考试。
几周前，在数据结构和算法课程的考试中，我遇到了以下问题。当时我无法在给定的时间内解决它，虽然我可能会通过课程，但从昨天开始我一直在努力想出一个解决方案，这样我就可以提高我的技能。
问题
给定一个整数 n 我们重复地从任何位置删除一个数字，直到我们只剩下一个数字。函数 PC(n) 定义为通过所述过程可获得的整数平方的最大数目。
例如 PC(32492) = 3。两个可能的序列是：
- 32492 -> 3249 -> 324 -> 24 -> 4
- 32492 -> 3249 -> 349 -> 49 -> 9
现在设计一个算法，可以在d的多项式时间内计算PC(n)，其中d是n的位数。假设您有办法在 O(1) 时间内测试一个数是否为整数的平方。
到目前为止我尝试了什么
第一种方法显然是测试每个可能的序列和 return 最大值。如果我没记错的话这是 O(d!).
改进蛮力法，我添加了一个 HashMap，其中存储了所有已计算的值。这样我们就可以使用 O(1) 查找来避免必须计算相同的值两次。这显然是实时使用的改进，但我很难获得时间复杂度的下限。所以，据我所知，这不是多项式。
我也尝试了一些贪心算法方法，但正如预期的那样，我发现每个算法（我能想到的）都没有选择最优的情况。
如有任何帮助，我们将不胜感激。我试着在网上寻找类似的问题，但到目前为止没有运气。
棘手，棘手。这方面的平方查找方面是一个转移注意力的问题，如果您可以在 O(1) 中检查它，这是一个有实际意义的问题。真正的问题是独特的、有序的子串查找，这似乎归结为经过一番争论后查找子序列，也许这是一个技巧问题，目标是表明它无法完成？
发布这个答案，这样问题就不会一直悬而未决。好像是老师弄错了，不可能。
这个问题可能应该只允许消除第一个或最后一个数字，在这种情况下，这个问题可以使用动态规划在 O(d^2) 中解决。
更新
看来根本不可能做到这一点。有人还给我发了一份不同的考试副本，其中提出了几乎相同的问题，但不同之处在于，你不能从任何位置移除，而只能从开头或开始移除。问题很可能是在复制时出现错误。现在我只需要证明这一点，并要求重新评估问题考试。
几周前，在数据结构和算法课程的考试中，我遇到了以下问题。当时我无法在给定的时间内解决它，虽然我可能会通过课程，但从昨天开始我一直在努力想出一个解决方案，这样我就可以提高我的技能。
问题
给定一个整数 n 我们重复地从任何位置删除一个数字，直到我们只剩下一个数字。函数 PC(n) 定义为通过所述过程可获得的整数平方的最大数目。
例如 PC(32492) = 3。两个可能的序列是：
- 32492 -> 3249 -> 324 -> 24 -> 4
- 32492 -> 3249 -> 349 -> 49 -> 9
现在设计一个算法，可以在d的多项式时间内计算PC(n)，其中d是n的位数。假设您有办法在 O(1) 时间内测试一个数是否为整数的平方。
到目前为止我尝试了什么
第一种方法显然是测试每个可能的序列和 return 最大值。如果我没记错的话这是 O(d!).
改进蛮力法，我添加了一个 HashMap，其中存储了所有已计算的值。这样我们就可以使用 O(1) 查找来避免必须计算相同的值两次。这显然是实时使用的改进，但我很难获得时间复杂度的下限。所以，据我所知，这不是多项式。
我也尝试了一些贪心算法方法，但正如预期的那样，我发现每个算法（我能想到的）都没有选择最优的情况。
如有任何帮助，我们将不胜感激。我试着在网上寻找类似的问题，但到目前为止没有运气。
棘手，棘手。这方面的平方查找方面是一个转移注意力的问题，如果您可以在 O(1) 中检查它，这是一个有实际意义的问题。真正的问题是独特的、有序的子串查找，这似乎归结为经过一番争论后查找子序列，也许这是一个技巧问题，目标是表明它无法完成？
发布这个答案，这样问题就不会一直悬而未决。好像是老师弄错了，不可能。
这个问题可能应该只允许消除第一个或最后一个数字，在这种情况下，这个问题可以使用动态规划在 O(d^2) 中解决。