algorithm - 动态规划：计算中间的超数

Question

给定两个数字，让我们调用它们X 以及Y 如何找到它们之间的所有“超级”数字。

超数是相邻数字的绝对差大于 1 的数。例如，数字 132 不是超数，因为 3 和 2 的差等于 1。数字 62 是超数，因为 6 之间的差并且 2 大于 1。

如何使用动态编程查找 X 和 Y（包括）之间的所有超数？

1 < X,Y < 10^5000 

标签： algorithmdynamic-programming

Answer 1

您可以使用一种称为“数字 DP”或“数字上的 Dp”的技术。假设我们有一个函数 f(x) 告诉您在 0 到 x（包括）之间的整数个数，这些整数是超数字，如果您想计算X, Y 之间的超数个数只需要计算 f(Y) 和 f(X-1)，因为 X 和 Y 之间的超数个数等于 f(Y)-f(X-1) (很直观地注意到原因）。

那么函数f(x)应该如何呢？你需要三个状态： index：字符串上的索引（数字）你在处理什么。紧：这将告诉当前数字范围是否受到限制。

例如，如果您有号码：

1234 可以到达各州，0234、0000、1231 等（数字小于或等于 1234）

但是您无法到达：2234、1244 等。

紧处理控制这一点。

last：最后使用的数字，这将帮助您进行转换，例如，如果您最后使用的数字是 4，那么您的下一个数字可以是 0、1、2 或 6、7、8、9（仅当紧不是积极的）。

我给你留下了一个教程和你可以找到更多信息的地方：

https://www.geeksforgeeks.org/digit-dp-introduction/在这里您可以更好地了解这个想法，以及紧密使用。您还可以在诸如 codeforces、topcoder、codechef 等竞争性编程页面上找到信息。

我通常在竞争性编程中看到这些问题，这是某些判断的问题吗？我想尝试一个解决方案。. 如果是这样的话，我真的希望你没有参加现场比赛。