Leetcode-ダイナミックプランニング1

5.最長回文子列
文字列sを指定すると、sの中で最も長い回文サブ列が見つかります.sの最大長さは1000と仮定できます.
例1:
入力:babad
出力:「bab」
注意:「aba」も有効な答えです.
例2:
入力:cbbd
出力:「bb」
構想1の中心拡張、すなわち、各文字を順次回文列の中心文字として、先に両側に拡張する.ここで注意すべきは、回文列が奇数と偶数の場合をそれぞれ考慮する必要がある.

def longestPalindrome(s):

    if not s or len(s) < 2:
        return s
        
    n = len(s)

    max_len = 1
    start_idx = 0
    
    #                ,      
    for i in range(n):
        j = 0
        
        #            
        while  i - j >= 0 and i + j < n:
            if s[i-j] == s[i + j]:
                if 2 * j + 1 > max_len:
                    max_len = 2 * j + 1
                    start_idx = i - j
                j += 1
            else:
                break

        #            
        j = 0
        while  i - j - 1 >= 0 and i + j < n:
            if s[i-j-1] == s[i + j]:
                if 2 * (j + 1) > max_len:
                    max_len = 2 * (j + 1)
                    start_idx = i - j - 1
                j += 1
            else:
                break
                
    return s[start_idx: start_idx+max_len]

構想2ダイナミックプランニング

def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    ans = ""

    #         l+1
    for l in range(n):
        #           i，       j=i+l          
        for i in range(n):
            j = i + l
            if j >= len(s):
                break
            if l == 0:
                dp[i][j] = True
            elif l == 1:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
            if dp[i][j] and l + 1 > len(ans):
                ans = s[i:j+1]
    return ans

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'に置き換える)
Exction->execution('u')を挿入
以下のメッシュは、word 1とword 2の対応する位置を互いに変換するために必要なステップ数を表し、2次元配列dpで表す
$dp[i][j]$は、word 1のi位置をword 2のj位置にするために必要なステップ数を表す.
配列dpの計算過程は以下の通りである.
$$\begin{align} dp[i][j] &=dp[i-1][j-1], if\quad word1[i]=word2[j]\\dp[i][j]&=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1,other\end{align}$$
Note:次の図に示すように、最初の行、最初の列を個別に考慮して「」を導入します.1行目は、「」からword 2へのステップ数(word 2から「」へのステップ数が一致しているとも理解できる)、すなわち挿入回数を表す.
1列目はword 1から‘’に変わるステップ数、すなわち削除回数を示す.
下から上へ

def minDistance(word1, word2):
    if word1 == '':
        return len(word2)
    if word2 == '':
        return len(word1)
    n1 = len(word1)
    n2 = len(word2)
    
    
    dp = [[0] * (n2+1) for i in range(n1+1)]
    for i in range(n1+1):
        dp[i][0] = i
    for i in range(n2+1):
        dp[0][i] = i
        
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            
            #       
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
    return dp[-1][-1]

時間的複雑度は$O(n^2)$であり,空間的複雑度は$O(n^2)$である.
トップダウン

def minDistance(word1, word2):
    if word1 == '':
        return len(word2)
    if word2 == '':
        return len(word1)
    n1 = len(word1)
    n2 = len(word2)
    w1 = [i for i in range(n1+1)]
    w2 = [i for i in range(n2+1)]
    #         ，    
    
    import functools
    # functools.lru_cache         ,           
    @functools.lru_cache(None)
    
    
    def helper(m, n):
        if m == 1:
            return w2[n-1]
        if n == 1:
            return w1[m-1]
        
        if word1[m-1] == word2[n-1]:
            return helper(m-1, n-1)
        else:
            return min(helper(m-1, n-1), helper(m-1, n), helper(m, n-1)) +1
    return helper(n1+1, n2+1)
        

198.家を略奪する
あなたはプロの泥棒で、街沿いの家を盗む計画です.各部屋には一定の現金が隠されていて、あなたの窃盗に影響する唯一の制約要素は隣接する家に相互に連通する防犯システムが設置されていることです.もし2つの隣接する家が同じ夜に泥棒に侵入されたら、システムは自動的に警察に通報します.
各家屋の保管金額を表す非負の整数配列を指定し、警報装置に触れない場合、一夜にして盗むことができる最高金額を計算します.
例1:
入力:[1,2,3,1]
出力:4
1号を盗み(金額=1)、3号を盗み(金額=3).
盗まれた最高金額=1+3=4.
例2:
入力:[2,7,9,3,1]
出力:12
1号(金额＝2)を盗み、3号(金额＝9)を盗み、5号(金额＝1)を盗む.
盗まれた最高金額=2+9+1=12.
$n$個数盗める最大値は$dp(n)$
$dp(n) = max(dp(n-2) + nums(n), dp(n-1))$

現在の要素の盗み:前は盗むことができなくて、盗むことができる最大値は$dp(n-2)+nums(n)$

に等しい

現在の要素は盗まない:前の要素が盗むことができる最大値、前の要素が盗むことができないのは大丈夫で、盗むことができる最大値は$dp(n-1)$

です.

盗むことができる最大値は$dp(n)=max(dp(n-2)+nums(n),dp(n-1)$

である.

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
       if len(nums) == 2:
        return max(nums[0], nums[1])
    rob_money = [nums[0], max(nums[0], nums[1])]

    n = len(nums)
    for i in range(2, n):
        rob_money[0], rob_money[1] = rob_money[1], max(rob_money[0]+nums[i], rob_money[1])

    return rob_money[1]    

213.家を略奪するII
あなたはプロの泥棒で、街沿いの家を盗む計画で、どの部屋にも現金が隠されています.この場所はすべての家が囲まれていて、最初の家と最後の家が隣接していることを意味しています.また、隣接する家屋には互いに連通する防犯システムが設置されており、隣接する2つの家屋が同じ夜に泥棒に侵入されると、自動的に警報が鳴る.
各家屋の保管金額を表す非負の整数配列を指定し、警報装置に触れずに盗むことができる最高金額を計算します.
例1:
入力:[2,3,2]
出力:3
説明:まず1号室(金額=2)を盗んでから、3号室(金額=2)を盗んではいけません.彼らは隣接しているからです.
例2:
入力:[1,2,3,1]
出力:4
说明:まず1号室(金额=1)を盗んで、それから3号室(金额=3)を盗むことができます.
盗まれた最高金額=1+3=4.
最初の要素を盗んだら、最後の要素は盗んではいけません.逆に、最后の1つが盗んで、第1つは盗むことができなくて、要するに同时に盗むことができません.
最初の最大値を盗まないことと最後の最大値を盗まないことをそれぞれ計算することができます

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
       if len(nums) == 2:
        return max(nums[0], nums[1])
    if len(nums) == 3:
        return max(nums)
    
    #      
    dp = [nums[1], max(nums[1], nums[2])]
    n = len(nums)
    for i in range(3, n):
        dp[0], dp[1] = dp[1], max(dp[0]+nums[i], dp[1])
        
    money_without_first = dp[1]
    
    #       
    dp = [nums[0], max(nums[0], nums[1])]
    for i in range(2, n-1):
        dp[0], dp[1] = dp[1], max(dp[0]+nums[i], dp[1])
        
    money_without_last = dp[1]
    
    return max(money_without_first, money_without_last)

516.最長回文サブシーケンス
文字列sが与えられ、その中で最も長い回文サブシーケンスが見つかり、そのシーケンスの長さが返される.sの最大長は1000と仮定できる.
 
例1:入力:
"bbbab"
出力:
4
可能な最長回文サブシーケンスは「bbbb」である.
例2:入力:
"cbbd"
出力:
2
可能な最長回文サブシーケンスは「bb」である.

def longestPalindromeSubseq(s) -> int:      
    n = len(s)

    if n <= 1 or s[::-1] == s:
        return n
    
    dp = [0]*n
    for i in range(n-1, -1, -1):
        temp = 0
        dp[i] = 1            
        for j in range(i+1, n):
            if s[i] == s[j]:
                temp, dp[j] = dp[j], temp + 2
            else:
                temp = dp[j]
                if dp[j-1] > dp[j]:
                    dp[j] = dp[j-1]
    return dp[-1]

674.最長連続増分シーケンス
並べ替えられていない整数配列を指定し、最も長く連続したインクリメントシーケンスを見つけ、シーケンスの長さを返します.
 
例1:
入力:[1,3,5,4,7]
出力:3
説明:最長連続増分シーケンスは[1,3,5]であり、長さは3である.
[1,3,5,7]も昇順のサブシーケンスであるが、5と7は元の配列で4によって隔てられているため、連続的ではない.
例2:
入力:[2,2,2,2,2]
出力:1
説明:最長連続増分シーケンスは[2]、長さは1です.
 
注意:配列の長さは10000を超えません.
これは同様に典型的な動的計画問題状態である:iを末尾とする最長増分サブシーケンス長、$f(i)$選択:現在の数字を前の最長サブシーケンスに加えるかどうか.
状態遷移方程式:$\begin{align}f(n)=begin{cases}f(n-1)+1,if(nums[n-1]>nums[n-2])\1,elseend{cases}end{align}$$

def findLengthOfLCIS(nums) -> int:
    if not nums or len(nums) == 0:
        return 0

    if len(nums) == 1:
        return 1

    #        : dp(i) = dp(i-1) + 1 if nums[i] > nums[i-1] else 1 

    res = 1
    dp = 1
    
    n = len(nums)
    for i in range(1, n):
        if nums[i] > nums[i-1]:
            dp = dp + 1
            res = max(res, dp)
        else:
            dp = 1
    return res