gistfile1.txt

Leetcode 514

Discussion from the blog:
http://www.cnblogs.com/grandyang/p/6675879.html

这道题是关于辐射4这款游戏出的，博主虽然没有玩过这款游戏，但是知道确实有些游戏中需要破解一些谜题才能继续通关，像博主很早以前
玩过的恐龙危机啊，生化危机啊啥的，都有一些机关需要破解，博主大部分都要靠看攻略来通关哈哈。

这道题讲的是一种叫做自由之路的机关，我们需要将密码字符串都转出来，让我们求最短的转动步数。博主最先尝试的用贪婪算法来做，就是
每一步都选最短的转法，但是OJ中总有些test case会引诱贪婪算法得出错误的结果，因为全局最优解不一定都是局部最优解，而贪婪算法一直
都是在累加局部最优解，这也是为啥DP解法这么叼的原因。贪婪算法好想好实现，但是不一定能得到正确的结果。DP解法难想不好写，但往往
才是正确的解法，这也算一个trade off吧。

这道题可以用DP来解，难点还是写递推公式，博主在充分研究网上大神们的帖子后尝试着自己理理思路，如果有不正确或者不足的地方，也请各位
不吝赐教。

此题需要使用一个二维数组 dp，其中 dp[i][j] 表示转动从 i 位置开始的 key 串所需要的最少步数(这里不包括 spell 的步数，因为spell
可以在最后统一加上)，此时表盘的 12 点位置是 ring 中的第 j 个字符。不得不佩服这样的设计的确很巧妙，我们可以从 key 的末尾往前推，这样
dp[0][0]就是我们所需要的结果，因为此时是从key的开头开始转动，而且表盘此时的12点位置也是ring的第一个字符。现在我们来看如何找出递推
公式，对于dp[i][j]，我们知道此时要将key[i]转动到12点的位置，而此时表盘的12点位置是ring[j]，我们有两种旋转的方式，顺时针和逆时针，
我们的目标肯定是要求最小的转动步数，而顺时针和逆时针的转动次数之和刚好为ring的长度n，这样我们求出来一个方向的次数，就可以迅速得到
反方向的转动次数。为了将此时表盘上 12 点位置上的 ring[j] 转动到 key[i]，我们要将表盘转动一整圈，当转到 key[i] 的位置时，我们计算出转动
步数 diff，然后计算出反向转动步数，并取二者较小值为整个转动步数step，此时我们更新dp[i][j]，更新对比值为step + dp[i+1][k]，这个也
不难理解，因为key的前一个字符key[i+1]的转动情况suppose已经计算好了，那么dp[i+1][k]就是当时表盘12点位置上ring[k]的情况的最短步数，
step就是从ring[k]转到ring[j]的步数，也就是key[i]转到ring[j]的步数，用语言来描述就是，从key的i位置开始转动并且此时表盘12点位置为
ring[j]的最小步数(dp[i][j])就等价于将ring[k]转动到12点位置的步数(step)加上从key的i+1位置开始转动并且ring[k]已经在表盘12点位置上
的最小步数(dp[i+1][k])之和。突然发现这不就是之前那道Reverse Pairs中解法一中归纳的顺序重现关系的思路吗，都做了总结，可换个马甲就又
不认识了，泪目中。。。

Related algorithm: reverse pairs - Hard level - leetcode 493