2つの従来の動的計画アルゴリズムの問題,2つの邪門の解

次は2つの非常に古典的な動的計画アルゴリズムの問題で、力ボタンから来て、解法もよく話されています.しかし、それぞれの速度ランキング1位の2つの解法は非常に尋常ではなく、穴を開けて、後で分析します.
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編集距離
2つの単語word 1とword 2が与えられ、word 1をword 2に変換するために使用される最小操作数が算出される.
1つの単語について、次の3つの操作を行うことができます.
1文字を挿入1文字を削除1文字を置換する例1:
入力:word 1="horse"、word 2="ros"出力:3解釈:horse->rorse('h'を'r')rorse->rose('r')rose->ros('e')例2:
入力:word 1="intention"、word 2="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 i0 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