两个常规动态规划算法题两个邪门的解

下面是两道非常经典的动态规划算法题，来自力扣，解法也是老生常谈。但是在各自速度排名第一的两个解法非常不同寻常，开个坑，以后分析。

LeetCode 322 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution(object):
    def coinChange(self, coins, amount):
        def dfs(idx, target, cnt):
            if idx == len(coins):
                return
            if (target + coins[idx] - 1) / coins[idx] + cnt >= self.ans:
                return
            if target % coins[idx] == 0:
                self.ans = min(self.ans, cnt + target / coins[idx])
                return 
            for j in range(target / coins[idx], -1, -1):  
                dfs(idx + 1, target - coins[idx] * j, cnt + j)

        self.ans = float('inf')
        coins = list(set(coins)) 
        coins.sort(reverse=True)
        dfs(0, amount, 0)
        return -1 if self.ans == float('inf') else self.ans

LeetCode 72 编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符
示例 1:

输入: word1 = “horse”, word2 = “ros”
输出: 3
解释:
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2:

输入: word1 = “intention”, word2 = “execution”
输出: 5
解释:
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def minDistance(self, word1, word2):
        if not word1 or not word2:
            return max(len(word1),len(word2))
        stack1=[(0,0,0)]
        stack2=[(len(word1),len(word2),0)]
        mem1={}
        mem2={}
        while True:
            newstack1=[]
            while stack1:
                i,j,lv=stack1.pop()
                if (i,j) in mem2:
                    return lv+mem2[(i,j)]
                if (i,j) in mem1:
                    continue
                else:
                    mem1[(i,j)]=lv
                if i<len(word1) and j<len(word2):
                    if word1[i]==word2[j]:
                        stack1.append((i+1,j+1,lv))
                        continue
                    else:
                        #rep
                        newstack1.append((i+1,j+1,lv+1))
                #add
                if j<len(word2):
                    newstack1.append((i,j+1,lv+1))
                #del
                if i<len(word1):
                    newstack1.append((i+1,j,lv+1))
            stack1=newstack1
            
            newstack2=[]
            while stack2:
                i,j,lv=stack2.pop()
                if (i,j) in mem1:
                    return lv+mem1[(i,j)]
                if (i,j) in mem2:
                    continue
                else:
                    mem2[(i,j)]=lv
                if i>0 and j>0:
                    if word1[i-1]==word2[j-1]:
                        stack2.append((i-1,j-1,lv))
                        continue
                    else:
                        #rep
                        newstack2.append((i-1,j-1,lv+1))
                #add
                if j>0:
                    newstack2.append((i,j-1,lv+1))
                #del
                if i>0:
                    newstack2.append((i-1,j,lv+1))
            stack2=newstack2