一、原题复现
M78 星云的手表问题：
- 一圈有 n 分钟（0~n-1）
- 两个按钮：+1 和 +k
- +1：当前数字 +1，超过 n 就回到 0
- +k：当前数字 +k，超过 n 就回到 0
问：从 0 出发，调到每一个数字最少要按多少次？这些最少次数里最大的那个是多少？
二、思路分析
这是一道经典的动态规划题目。如果从时间出发较为复杂，不妨从次数入手，来不断优化到每个时间的次数。
例如 n=5，k=3。dp[0] 赋值为 0，那么 dp[1]=1, dp[3]=1，继续 dp[2]=2, dp[4]=2。此时我们可以发现到时间 1 的路径有两条，即 0+1，和 0+3+3。这里就体现了优化的过程，用一个公式表达就是 1=(3+3)%5; dp[1]=min(dp[1], dp[3]+1)。
下面对算法流程进行说明：
我们可以用上面举过的例子对其进行过程分析，n=5，k=3。dp[0]=0，第一轮的情况：dp[1]=1, dp[3]=1，将其都进队；第二轮以 dp[1] 作为基准值：dp[2]=2, dp[4]=2，将其都进队；第三轮以 dp[3] 作为基准值：dp[4]=2, dp[1]=2。此时可以看到我们得到的 dp[1]>1，小于我们原来得到的 dp[1]，故其不进队，dp[4] 同理。我们利用队列的本质便是用队里的元素去更新外界元素找到最小值，试想如果将 dp[1] 赋值给 2 并进队，那么接下来得到的路径是不是要比 dp[1]=1 时都要大，所以不能进队。所以也很容易想到当队列为空所有路径都走完了，且找不到更加小的值了，达到了优化的目标。