本文主要是介绍leetcode-514自由之路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
514. 自由之路 - 力扣（LeetCode）
解题思路
定义dp[i][j]表示从前往后拼写出key的第i个字符，ring的第j个字符与12：00方向对其的最小步数。下标均从0开始。
显然，只有当字符串ring的第j个字符需要和key的第i个字符相同时才能拼写出key的第i个字符，因此对于key的第i个字符，需要考虑计算ring的第j个字符只有key[i]在ring中出现的下标集合。我们对每个字符维护一个位置数组pos[i]，表示字符i在ring中出现的位置集合，用来加速转移的过程。
对于状态dp[i][j]，需要枚举上一次与12：00方向对其的位置k,因此可以列出如下的转移方程：
其中min{abs(j - k), n - abs(j - k)} + 1 表示在当前第k个字符与12：00方向对其时第j个字符旋转到12：00方向并按下拼写的最小步数。
这样的做法需要开辟O（mn）的空间里存放dp值，考虑到每次转移状态dp[i][]只会从dp[i-1][]转移过来，因此我们可以利用滚动数组优化第一维的空间复杂度，有能力的读者可以尝试实现。
虽然我连这个看不懂
这篇关于leetcode-514自由之路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
