这是代码厨师6月挑战问题（比赛已经结束）
厨师喜欢游戏！但他喜欢发明自己的 . 现在他玩游戏“数字跳” . 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^ 5 S的每个符号都是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 . 即 . 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次跳转来达到任何数字，但这与迭代次数有什么关系 . 事实上，有些用户评论说他们迭代了只有三次（fwd，backwd和fwd）以及一些迭代10次且接受了解决方案的用户 . 在bfs解决方案中，图表的确切程度如何 . 任何人都可以用一个小例子来解释 .
1 回答
我用一个简单的BFS解决了这个问题 . 第一次使用距离
d到达数字D时，您可以使用数字D到d+1更新到其他位置的距离 .