letcode_514_自由之路.py

#!/usr/bin/env python
#!/usr/bin/python
# -*- coding: UTF-8 -*-


"""
@File：letcode_514_自由之路.py
@Data：2019/7/8
@param：
@return：
"""


# 这道题主要是查看别人的代码，对此，我对动态规划再次进行了一次学习。
# 需要对递归进行进一步掌握。
# 动态规划问题主要的解题方法有：1、最优子结构2、重叠性
#
# 动态规划问题：
# 事实上上面分析的过程，首先是用递归的方法来求解所有可能情况的暴力解法，发现暴力解法当中存在的重复计算的问题，然后增加一个记忆表，将程序修改成为自上而下的带记忆表的递归过程，最后是修改成为自下而上的我们熟悉的动态规划的过程。的确动态规划的过程可以这样引出来，
#
# 所以实际当中对于动态规划有两种解决办法，1：先写出递归的式子，然后将递归的式子进行修改得到自上而下的方法，最后得到自下而上的方法。这样能够保障思路清晰，而且相对来说容易一些。  2：直接写动态规划过程，可以说是在第一种方法熟练的基础上直接进行。
#
# 递归解法的一般思路：
# 要构建一个递归过程，就需要很好的描述它,当你能够很好的描述它的时候，这个递归问题已经很好写了。
# 描述的时候要用到最优子结构：如何将这个问题转化为相同的子问题。最优子结构是：原问题的最优解可以由相同子问题的最优解来进行构造。 这样就可以递归的求解原来的问题。求解父问题的过程其实是一个选择过程，从下面的很多问题当中可以看出，其实是在诸多的选择问题当中选择一个最优解。
#
# 动态规划解法的一般思路：
# 动态规划可以由递归生成，所以，能用动态规划来解的问题，一定可以用递归来解。
# 动态规划解法分为两步：1.确定状态，2.根据状态列出状态转移方程。 什么是状态？当我们把原问题分解为子问题的时候，那些子问题就是状态，什么是状态转移方程，我们如何由子问题构造出来父问题的过程，这个过程就是状态转移的过程。这个过程往往是自上而下的，先定义和求解最简单的子问题，然后一步一步向上转移和求解。
import collections

class Solution:
	#	自由之路
    def findRotateSteps(self, ring: str, key: str) -> int:
        dic = collections.defaultdict(list)
        # enumerate返回枚举类型
        for i, ch in enumerate(ring):
            dic[ch].append(i)
        l = len(ring)
        past = [(0, 0)]
        for ch in key:
            # 找出要查找的字符
            cur = []
            # 遍历存在该值的字典数组
            for curIndex in dic[ch]:
                # 设置一个最小次，在下面循环时得出的值需要与这个最小值比较
                this_min = float('inf')
                for pastIndex, m in past:  # 此次m表示上一次最小的距离
                    # 当前位置与前1位置距离最近的点
                    temp = abs(curIndex - pastIndex)
                    this_min = min(this_min, m + temp, m + l - temp)  #此处一直是求遍历后最小的min值
                # 添加当前的索引和最值
                cur.append((curIndex, this_min))
            past = cur
        # past最后为一个数组，其中m为除最终移动的距离，然后取最小的返回，key的长度是值需要拼接的总次数
        return min([n[1] for n in past]) + len(key)