Codechef解决方案动态规划

Question

这是 code-chef 六月挑战问题(比赛已结束)

厨师喜欢游戏!但他喜欢发明自己的东西。现在他玩游戏“数字跳跃”。 Chef 具有数字序列 S1、S2、...、SN、。他停留在第一位数字(S1)，并希望以最少的跳跃次数到达最后一位数字(SN)。当停留在索引为 i(数字 Si)的某个数字 x 时，Chef 可以跳转到索引为 i - 1 (Si-1) 和 i + 1 (Si+1) 的数字，但他不能跳出顺序。或者他可以跳转到任何具有相同值 x 的数字。帮助 Chef 找到从数字 S1 到达数字 SN 所需的最少跳跃次数。

输入

输入包含一行，由长度为 N 的字符串 S(数字序列)组成。

输出

在单行中打印单个整数 - 他需要的最小跳转次数。

约束

1 ≤ N ≤ 10^5S的每个符号都是0到9的数字。

示例

输入:01234567890

输出:1

输入:012134444444443

输出:4

这是他提供的解决方案之一

设 dp[i] 表示从位置 0 到位置 i 所需的步数。根据之前的观察，我们知道不需要超过 20 个步骤。所以让我们进行 20 次迭代。

在开始所有迭代之前，我们将为所有其他 i > 1 设置 dp[1] = 0 和 dp[i] = 无穷大。在每次迭代中，我们将计算 Q[k]，其中 Q[k] 是 dp[i] 的最小值，使得 s[i] = k。 IE。 Q[k]表示该数字等于k的位置上dp的最小值。

我们可以通过以下方法更新dp。dp[i] = min(dp[i], dp[i - 1] + 1, dp[i + 1] + 1, Q[s[i]] + 1);

这里术语 dp[i - 1] + 1 表示我们来自先前的位置，即 (i - 1)。这里术语 dp[i + 1] + 1 表示我们来自下一个位置，即 (i + 1)。Q[s[i]] + 1 表示从与当前第 i 位数字相同的位置开始所需的最少运算次数。

您可以在此处查看问题和社论

http://discuss.codechef.com/questions/44800/digjump-editorial?sort=votes&page=2

我不明白为什么他认为20次迭代就足够了。我理解我们最多需要20次跳转才能达到任何数字，但这与迭代次数有什么关系。事实上，有一些用户评论他们只迭代了三次(前进、后退和再次前进)，而一些用户迭代了 10 次并获得了他们的解决方案被接受。在 bfs 解决方案中，图表看起来到底如何。任何人都可以用一个小例子解释一下。

Answer 1

我已经通过简单的 BFS 和一次修改解决了这个问题。一旦您第一次到达距离 d 的数字 D，您就可以将到其他具有数字 D 的位置的距离更新为 d+1.