Leetcode 4: dp

Posted on | | Visitors: | views

这篇文章不仅是总结Leetcode上关于DP的题，也恰好是总结一下算法课中关于DP的内容。

Longest Common Subsequence

  • Problem: 最长公共子序列。给定两个字符串，判定公共子序列的最大长度，这里的子序列可以是不连续的。Leetcode上有一道近似题：Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
  • Example: Input: “sea”, “eat”, output: 2. Explanation: You need one step to make “sea” to “ea” and another step to make “eat” to “ea”. 其实就是找出LCS的长度，然后减一下。
  • Link: https://leetcode.com/problems/delete-operation-for-two-strings/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    # 1: 递归，O(2^m)，超时
    class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            def LCS(X, Y, i, j):
                if i == -1 or j == -1:
                    return 0
                if X[i] == Y[j]:
                    return LCS(X, Y, i - 1, j - 1) + 1
                else:
                    return max(LCS(X, Y, i - 1, j), LCS(X, Y, i, j - 1))
                
            word1 = list(word1)
            word2 = list(word2)
            return len(word1) + len(word2) - 2 * LCS(word1, word2, len(word1) - 1, len(word2) - 1)

    # 2: 带有memo的递归，DP，AC
    class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            seen = {}
            
            def LCS(X, Y, i, j):
                if (i, j) in seen:
                    return seen[(i, j)]
                else:
                    if i == -1 or j == -1:
                        seen[(i, j)] = 0
                        return seen[(i, j)]
                    if X[i] == Y[j]:
                        seen[(i, j)] = LCS(X, Y, i - 1, j - 1) + 1
                        return seen[(i, j)]
                    else:
                        seen[(i, j)] = max(LCS(X, Y, i - 1, j), LCS(X, Y, i, j - 1))
                        return seen[(i, j)]
                
            word1 = list(word1)
            word2 = list(word2)
            return len(word1) + len(word2) - 2 * LCS(word1, word2, len(word1) - 1, len(word2) - 1)

    # 3: 优化memo的DP，二维表
    class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            m = len(word1)
            n = len(word2)
            memo = [[0] * (n + 1) for i in range(m + 1)]
            
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if word1[i - 1] == word2[j - 1]:
                        memo[i][j] = memo[i - 1][j - 1] + 1
                    else:
                        memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])
            
            return m + n - 2 * memo[-1][-1]

    # 4: 进一步优化DP，两个数组，best
    class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            if len(word1) < len(word2):
                pass
            else:
                word1, word2 = word2, word1
            s, l = len(word1), len(word2)
            memo = [[0] * (l + 1), [0] * (l + 1)]

            for i in range(s):
                for j in range(1, l + 1):
                    if word1[i] == word2[j - 1]:
                        memo[1][j] = memo[0][j - 1] + 1
                    else:
                        memo[1][j] = max(memo[0][j], memo[1][j - 1])
                memo[0], memo[1] = memo[1], memo[0]

            return s + l - 2 * memo[0][-1]

    # 5: 若要追溯子序列，在3的基础上增加一个标记memo. 本代码来自网上
    def find_lcseque(X, Y):
        m = len(X)
        n = len(Y)
        L = [[0] * (n + 1) for i in range(m + 1)]
        B = [["D"] * (n + 1) for i in range(m + 1)]

        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    L[i][j] = 0
                    if i == 0:
                        B[i][j] = "L"
                    else:
                        B[i][j] = "U"
                elif X[i - 1] == Y[j - 1]:
                    L[i][j] = L[i - 1][j - 1] + 1
                else:
                    if L[i - 1][j] < L[i][j - 1]:
                        L[i][j] = L[i][j - 1]
                        B[i][j] = "L"
                    else:
                        L[i][j] = L[i - 1][j]
                        B[i][j] = "U"

        return L, B


    def track_lcseque(X, Y, Track):
        result = []
        start = (len(X) - 1, len(Y) - 1)
        if Track[-1][-1] == "D":
            result.append(X[-1])
        while start[0] or start[1]:
            next = Track[start[0]][start[1]]
            if next == "D":
                start = (start[0] - 1, start[1] - 1)
                result.append(X[start[0]])
            elif next == "L":
                start = (start[0], start[1] - 1)
            else:
                start = (start[0] - 1, start[1])
        return result[::-1]


    x = 'abdfg'
    y = 'abcdfg'
    l, b = find_lcseque(x, y)
    print("LCS：", end="")
    print(track_lcseque(x, y, b))
    print("LCS Len：" + str(l[-1][-1]))

Longest Common Subarray

  • Problem: 最长公共子串，要求连续。Leetcode上原题：Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
  • Example: Input: A: [1,2,3,2,1], B: [3,2,1,4,7], output: 3.
  • Link: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    # Comment: 这一题和上一题最大的区别就是找出的序列要求连续。因此两者的区别也就集中在递归方程的变化上：本题仅仅要求继承对角线上的累积和即可

    class Solution:
        def findLength(self, word1, word2):
            if len(word1) < len(word2):
                pass
            else:
                word1, word2 = word2, word1
            s, l = len(word1), len(word2)
            memo = [[0] * (l + 1), [0] * (l + 1)]

            max_len = 0
            for i in range(s):
                for j in range(1, l + 1):
                    if word1[i] == word2[j - 1]:
                        memo[1][j] = memo[0][j - 1] + 1
                        max_len = max(max_len, memo[1][j])
                    else:
                        memo[1][j] = 0
                memo[0], memo[1] = memo[1], memo[0]

            return max_len

    # 若要定位出位置，则需要加一个track变量。下面代码来自网上，不过区别不大
    def find_lcsubstr(X, Y):
        m = len(X)
        n = len(Y)
        L = [[0] * (n + 1) for i in range(m + 1)]
        max_length = 0  # 最长匹配的长度
        p = 0  # 最长匹配对应在s1中的最后一位
        for i in range(m):
            for j in range(n):
                if X[i] == Y[j]:
                    L[i + 1][j + 1] = L[i][j] + 1
                    if L[i + 1][j + 1] > max_length:
                        max_length = L[i + 1][j + 1]
                        p = i + 1
        return X[p - max_length:p], max_length


    print(find_lcsubstr('abcdfg', 'abdfg'))

Longest Palindromic Subsequence

  • Problem: 最长回文子序列。Leetcode原题：Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
  • Example: Input “XABCBBACXA”, output 7 (“XABCBAX”)
  • Link: https://leetcode.com/problems/longest-palindromic-subsequence/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # Comment: 不能用LCSeq来解决，因为虽然可以返回最大回文子序列的值，但是不一定找对序列。比如“ABCAB”，最大回文子序列是ABA，但是它和它的reverse“BACBA”的最大公共子序列可以是“ACB”，这就不是一个回文子序列
    # 用区间型动态规划来进行查找

    class Solution:
        def longestPalindromeSubseq(self, s):
            l = len(s)
            memo = [[0] * l for i in range(l)]

            for ll in range(l):
                for i in range(l - ll - 1, -1, -1):  # Bottom-up
                    j = i + ll
                    if j == i:
                        memo[i][j] = 1
                    else:
                        if s[i] == s[j]:
                            memo[i][j] = memo[i + 1][j - 1] + 2
                        else:
                            memo[i][j] = max(memo[i + 1][j], memo[i][j - 1])

            return memo[0][-1]

Longest Palindromic Subarray

  • Problem: 最长回文子串。Leetcode原题：Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
  • Example: Input: “cbbd”, output: “bb”.
  • Link: https://leetcode.com/problems/longest-palindromic-substring/
  • Answers:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    # Comemnt: 不能用LCSub来解决，因为回文串不一定是最大子串。比如说“aacbdcaa”，镜像的最大子串是“aac”，但是回文只有“aa”
    # 用区间型动态规划来修改最大子串的查找方法

    class Solution:
        def longestPalindrome(self, s):
            l = len(s)
            memo = [[0] * l for i in range(l)]

            max_len = 0
            start = end = 0
            for ll in range(l):  # 长度从0到l
                for i in range(l - ll - 1, -1, -1):  # Bottom-up
                    j = i + ll
                    if j == i:
                        memo[i][j] = True
                    elif j == i + 1:
                        memo[i][j] = (s[i] == s[j])
                    else:
                        memo[i][j] = (memo[i + 1][j - 1] and (s[i] == s[j]))
                    if memo[i][j] and j - i + 1 > max_len:
                        max_len = j - i + 1
                        start, end = i, j

            return s[start:end + 1]

    # 另有一种Manacher算法，只需要O(n)：https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2

    def manacher(s0 : str) -> list:
        T = '$#' + '#'.join(s0) + '#@'
        l = len(T)
        P = [0] * l
        R, C = 0, 0
        for i in range(1,l-1):
            if i < R:
                P[i] = min(P[2 * C - i], R - i)
            
            while T[i+(P[i]+1)] == T[i-(P[i]+1)]:
                P[i] += 1
            
            if P[i] + i > R:
                R = P[i] + i
                C = i
        return P

Longest Increasing Subsequence

  • Problem: 最长递增子序列。Leetcode: Given an unsorted array of integers, find the length of longest increasing subsequence.
  • Example: Input: [10,9,2,5,3,7,101,18], output: 4. Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
  • Link: https://leetcode.com/problems/longest-increasing-subsequence/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    # Comment: 最自然想到的是定义DP标记函数为L(n)，表示从1到n区间内的最长递增子序列长度。但是这样带来的问题是，当新的子序列不延续前面的子序列，而是从n+1处重新开始时，无法完成递归调用。所以需要把标记函数定义改为：从1到n区间内，使用了nums[n]的，最长递增子序列长度。因此，L(n) = 1 + max{L(j), j from 1 to n - 1 & nums[j] < nums[n]}.

    class Solution:
        def lengthOfLIS(self, nums):
            l = len(nums)
            memo = [0] * l

            max_len = 0
            for i in range(l):
                for j in range(i):
                    if nums[j] < nums[i]:
                        memo[i] = max(memo[i], memo[j])
                memo[i] += 1
                max_len = max(max_len, memo[i])

            return max_len

    # 如果需要记录LIS具体是什么，加pointers回溯
    # 更好的方法：上面的方法时间复杂度是O(n^2)，我们可以在第二重循环上用Binary Search来改进查找效率，整体复杂度就会从n^2降到nlogn
    class Solution:
        def lengthOfLIS(self, nums):
            tails = [0] * len(nums)
            size = 0
            for x in nums:
                i, j = 0, size
                while i != j:
                    m = (i + j) // 2
                    if tails[m] < x:
                        i = m + 1
                    else:
                        j = m
                tails[i] = x
                size = max(i + 1, size)
            return size

Longest Increasing Subarray

  • Problem: 最长递增子串。Leetcode: Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
  • Example: Input: [1,3,5,4,7], output: 3
  • Link: https://leetcode.com/problems/longest-continuous-increasing-subsequence/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
        def findLengthOfLCIS(self, nums):
            l = len(nums)
            
            if l <= 1:
                return l
            
            memo = [1] * l

            max_len = 0
            for i in range(1, l):
                if nums[i - 1] < nums[i]:
                    memo[i] = memo[i - 1] + 1
                max_len = max(max_len, memo[i])

            return max_len

矩阵链问题

  • Problem: 给定一串数[a, b, c, d]，表示矩阵ab、矩阵bc、矩阵cd相乘，判断如何控制计算顺序以达到最小计算量。矩阵ab 乘 矩阵bc 的计算量为ab*c。
  • Example: Input [3, 1, 5, 8], output: (A1(A2A3))
  • Link: 不确定Leetcode上有没有
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    # 区间型动态规划

    def MATRIX_CHAIN_ORDER(p):
        n = len(p) - 1  # n is 矩阵个数
        m = [[0 for col in range(n + 1)] for row in range(n + 1)]  # m[i][j] is 对应矩阵计算 最优值
        s = [[0 for col in range(n + 1)] for row in range(n + 1)]  # 分割点记录
        for L in range(2, n + 1):  # L为矩阵链长度,依次枚举
            for i in range(1, n - L + 2):  # n-L+1为最后一次枚举的矩阵链的起点
                j = i + L - 1  # j为枚举的矩阵链的终点
                m[i][j] = float('inf')  # 超出枚举的矩阵链计算量设为无穷大
                for k in range(i, j):  # k is 分割点，枚举
                    q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                    if q < m[i][j]:
                        m[i][j] = q  # 新的最小值
                        s[i][j] = k  # 分割点记录

        print("最优路径：", end="")
        PRINT_OPTIMAL_PARENS(s, 1, n)
        return m, s


    def PRINT_OPTIMAL_PARENS(s, i, j):
        if i == j:
            print("A" + str(i), end='')
        else:
            print("(", end='')
            PRINT_OPTIMAL_PARENS(s, i, s[i][j])
            PRINT_OPTIMAL_PARENS(s, s[i][j] + 1, j)
            print(")", end='')


    # test
    p = [3, 1, 5, 8]
    m, s = MATRIX_CHAIN_ORDER(p)
    print("\n最小代价：" + str(max(sum(m, []))))

取数游戏：头尾取数

  • Problem: Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
  • Example: Input: [1, 5, 2], output: False. Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False.
  • Link: https://leetcode.com/problems/predict-the-winner/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    # Comment: 与最大回文子串、矩阵链问题一样，是区间型动态规划

    class Solution:
        def PredictTheWinner(self, nums):
            l = len(nums)
            
            if l % 2 == 0:
                return True

            memo = [[0] * l for k in range(l)]

            sum_nums = 0
            for ll in range(l):  # 长度从0到l
                sum_nums += nums[ll]
                for i in range(l - ll):  # i从头到l - 长度
                    j = i + ll
                    if j == i:
                        memo[i][j] = nums[i]
                    elif j == i + 1:
                        memo[i][j] = max(nums[i], nums[j])
                    else:
                        left = min(memo[i + 1][j - 1], memo[i + 2][j]) + nums[i]
                        right = min(memo[i][j - 2], memo[i + 1][j - 1]) + nums[j]
                        memo[i][j] = max(left, right)

            return memo[0][-1] * 2 >= sum_nums

rod cutting：切钢管

  • Problem: 给定一根钢管，告知其每整数段的售价，问最大售价及最佳切割办法。
  • Example: l = [1, 2, 3, 4, 5, 6, 7, 8], p = [1, 5, 8, 9, 10, 17, 17, 20], 则最佳切割是在(2, 6)或(6, 2)处，总售价为5 + 17 = 22。
  • Link: 暂未找到
  • Answer: 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    l = [1, 2, 3, 4, 5, 6, 7, 8]
    p = [1, 5, 8, 9, 10, 17, 17, 20]

    r = l[:]
    v = [p[0]] * len(l)
    for i in range(1, len(l)):
        for j in range(i):
            if p[j] + v[i - j - 1] > v[i]:
                v[i] = p[j] + v[i - j - 1]
                r[i] = i - j
        if p[i] > v[i]:
            v[i] = p[i]
            r[i] = i + 1
    print("最大价值：" + str(v[-1]))

    res = []
    left = len(l)
    while left > 0:
        res.append(r[left - 1])
        left -= r[left - 1]
    print("最佳切割：" + str(res))

0-1背包问题

  • Problem: 有N种物品(每个1件)和一个容量为V的背包。第i建物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
  • Example: Bag = 14, Weight = [3, 2, 6, 7, 2, 4, 9, 5], Value = [6, 3, 5, 8, 3, 1, 6, 9]. Solution is items in index [1, 2, 5, 8], maximum value is 21.
  • Link: 暂未找到
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    def OneNPPack(w, v, b):
        w.insert(0, 0)
        v.insert(0, 0)
        k = len(w)
        memo = [[0 for bb in range(b + 1)] for kk in range(k)]
        indx = [[0 for bb in range(b + 1)] for kk in range(k)]
        for i in range(1, k):
            for j in range(1, b + 1):
                if j < w[i]:  # 边界情况，装不下第k个物品
                    memo[i][j] = memo[i - 1][j]
                    indx[i][j] = indx[i - 1][j]
                else:  # 能装下第k个物品时，在两种情况中选一个
                    if memo[i - 1][j] < memo[i - 1][j - w[i]] + v[i]:  # 装入第k个物品
                        memo[i][j] = memo[i - 1][j - w[i]] + v[i]
                        indx[i][j] = i
                    else:  # 不装第k个物品
                        memo[i][j] = memo[i - 1][j]
                        indx[i][j] = indx[i - 1][j]
        return memo, indx


    def OneNTrack(w, b, track):
        start = track[-1][-1]
        holds = []
        length = b
        while length > 0 and start > 0:
            holds.append(start)
            length -= w[start]
            next = track[start - 1][length]
            start = next
        return holds


    Bag = 14
    Weight = [3, 2, 6, 7, 2, 4, 9, 5]
    Value = [6, 3, 5, 8, 3, 1, 6, 9]
    value, track = OneNPPack(Weight, Value, Bag)
    print("最大价值：" + str(value[-1][-1]))
    print("装入物品：", end="")
    print(OneNTrack(Weight, Bag, track))

完全背包问题

  • Problem: 有N种物品(每个无数件)和一个容量为V的背包。第i建物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
  • Example: Bag = 14, Weight = [3, 2, 6, 7, 2, 4, 9, 5], Value = [6, 3, 5, 8, 3, 1, 6, 9]. Solution is items in index [2, 1, 1, 1, 1], maximum value is 27.
  • Link: 暂未找到
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    def KNPPack(w, v, b):
        w.insert(0, 0)
        v.insert(0, 0)
        k = len(w)
        memo = [[0 for bb in range(b + 1)] for kk in range(k)]
        indx = [[0 for bb in range(b + 1)] for kk in range(k)]
        for i in range(1, k):
            for j in range(1, b + 1):
                if i == 1:
                    memo[i][j] = (j // w[i]) * v[i]
                    if j < w[i]:  # 无法装入第1个物品
                        indx[i][j] = 0
                    else:  # 可装入第一个物品
                        indx[i][j] = i
                else:
                    if j < w[i]:
                        memo[i][j] = memo[i - 1][j]
                        indx[i][j] = indx[i - 1][j]
                    else:
                        if memo[i - 1][j] < memo[i][j - w[i]] + v[i]:  # 装入第k个物品
                            memo[i][j] = memo[i][j - w[i]] + v[i]
                            indx[i][j] = i
                        else:  # 不装第k个物品
                            memo[i][j] = memo[i - 1][j]
                            indx[i][j] = indx[i - 1][j]
        return memo, indx


    def KNTrack(w, b, track):
        start = track[-1][-1]
        holds = []
        length = b
        while length > 0:
            holds.append(start)
            length -= w[start]
            next = track[start][length]
            start = next
        return holds


    Bag = 14
    Weight = [3, 2, 6, 7, 2, 4, 9, 5]
    Value = [6, 3, 5, 8, 3, 1, 6, 9]
    value, track = KNPPack(Weight, Value, Bag)
    print("最大价值：" + str(value[-1][-1]))
    print("装入物品：", end="")
    print(KNTrack(Weight, Bag, track))