当前位置：网站首页>break algorithm---dynamic planning(dp-func)

break algorithm---dynamic planning(dp-func)

2022-06-13 11:21:00 【壬辛酉】

声明：
算法基于https://labuladong.github.io/
python语言实现

53.maximum-subarray
72.edit-distance
494.target-sum
516. Longest Palindromic Subsequence
931.minimum-falling-path-sum
1143. Longest Common Subsequence
10.regular-expression-matching

53.maximum-subarray

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        memory = dict()

        def dp(i: int):
            # base case
            if i == 0:
                memory[0] = nums[0]
                return nums[0]

            if memory.get(i): return memory[i]

            # recursive
            if nums[i - 1] > 0:
                memory[i] = nums[i] + dp(i - 1)
            else:
                memory[i] = max(nums[i], nums[i] + dp(i - 1))

            return memory[i]

        max_subarr_len = 0
        for i in range(len(nums)):
            max_subarr_len = max(max_subarr_len, dp(i))

        return max_subarr_len


def main():
    # Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
    # Output: 6
    # Explanation: [4,-1,2,1] has the largest sum = 6.
    solution1 = Solution()
    print(solution1.maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))

    # Input: nums = [5,4,-1,7,8]
    # Output: 23
    solution1 = Solution()
    print(solution1.maxSubArray(nums=[5, 4, -1, 7, 8]))

    # Input: nums = [1]
    # Output: 1
    solution1 = Solution()
    print(solution1.maxSubArray(nums=[1]))


if __name__ == '__main__':
    main()

72.edit-distance

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        memory = dict()

        def dp(i: int, j: int) -> int:
            # base case
            if i == -1:
                res = j + 1
                return res
            if j == -1:
                res = i + 1
                return res

            # pre recursive:查memory
            if memory.get((i, j)): return memory[(i, j)]

            # recursive：结果写入memory
            # 1.指针i，j所指字符相等时：
            # i，j均前移一位，操作数（insert，delete，replace）不变
            if word1[i] == word2[j]:
                memory[(i, j)] = dp(i - 1, j - 1)
            # 2.指针i，j所指字符不等时：
            # 操作数加一，指针移动位数依照具体的操作
            # dp(i, j - 1) + 1, # insert
            # dp(i - 1, j) + 1, # delete
            # dp(i - 1, j - 1) + 1 # replace
            else:
                memory[(i, j)] = min(
                    dp(i, j - 1) + 1,
                    dp(i - 1, j) + 1,
                    dp(i - 1, j - 1) + 1
                )
            # post recusive：返回memory[(i, j)]
            return memory[(i, j)]

        return dp(len(word1) - 1, len(word2) - 1)


def main():
    # Input: word1 = "horse", word2 = "ros"
    # Output: 3
    # Explanation:
    # horse -> rorse (replace 'h' with 'r')
    # rorse -> rose (remove 'r')
    # rose -> ros (remove 'e')
    solution1 = Solution()
    print(solution1.minDistance(word1="horse", word2="ros"))

    # Input: word1 = "intention", word2 = "execution"
    # Output: 5
    # Explanation:
    # intention -> inention (remove 't')
    # inention -> enention (replace 'i' with 'e')
    # enention -> exention (replace 'n' with 'x')
    # exention -> exection (replace 'n' with 'c')
    # exection -> execution (insert 'u')
    solution2 = Solution()
    print(solution2.minDistance(word1="intention", word2="execution"))


if __name__ == '__main__':
    main()

494.target-sum

""" 本例含有重复子问题，需使用备忘录优化，原因如下： 【仅抽象出递归框架，查看不同状态转移之间的路径是否唯一】：唯一，不存在重叠子问题，无需备忘录 不唯一，存在重叠子问题，需使用备忘录去重 本题递归框架为： def dp(i: int, target: int) -> int: dp(i - 1, target - nums[i]) dp(i - 1, target + nums[i]) 如果nums[i] = 0，这样就出现了两个「状态」完全相同的递归函数，无疑这样的递归计算就是重复的。 这就是重叠子问题，而且只要我们能够找到一个重叠子问题，那一定还存在很多的重叠子问题。 因此，状态 (i, remain) 是可以用备忘录技巧进行优化的： ！！！用Python的【哈希表dict】来做备忘录，其中dict的【key为dp方法所有入参组成的元组对：(dp_arg1, dp_arg2, ...)，即所有的可变状态的组合】 memory = dict() {(dp_arg1_state1, dp_arg2_state2, ...):value1, (dp_arg1_state2, dp_arg2_state2, ...):value2, (dp_arg1_state3, dp_arg2_state3, ...):value3, ...} """

from typing import List


class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        memory = dict()

        def dp(i: int, target: int) -> int:
            # base case
            if i == 0:
                if nums[i] == 0 and nums[i] == target:
                    return 2
                elif nums[i] == target or -nums[i] == target:
                    return 1
                else:
                    return 0

            # pre recursive:查memory
            # NOTE:需要把i和target的组合作为key，而不能仅把i作为key
            # ！！！即需要把dp方法中所包含的所有可变状态的组合作为key！！！
            if memory.get((i,target)): return memory[(i,target)]

            # recursive:写memory
            ways_add = dp(i - 1, target - nums[i])
            ways_plus = dp(i - 1, target + nums[i])
            memory[(i,target)] = ways_add + ways_plus

            # post recursive:
            return memory[(i,target)]

        return dp(len(nums) - 1, target)


def main():
    # Input: nums = [1,1,1,1,1], target = 3
    # Output: 5
    # Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
    # -1 + 1 + 1 + 1 + 1 = 3
    # +1 - 1 + 1 + 1 + 1 = 3
    # +1 + 1 - 1 + 1 + 1 = 3
    # +1 + 1 + 1 - 1 + 1 = 3
    # +1 + 1 + 1 + 1 - 1 = 3
    solution1 = Solution()
    print(solution1.findTargetSumWays(nums=[1, 1, 1, 1, 1], target=3))

    # Input: nums = [1], target = 1
    # Output: 1
    solution2 = Solution()
    print(solution2.findTargetSumWays(nums=[1], target=1))

    # Input: [0,0,0,0,0,0,0,0,1] 1
    # Output: 128
    # Expected: 256
    solution3 = Solution()
    print(solution3.findTargetSumWays([0, 0, 0, 0, 0, 0, 0, 0, 1], 1))


if __name__ == '__main__':
    main()

494.without_memo_Time-Limit-Error

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def dp(i: int, target: int) -> int:
            # base case
            if i == 0:
                if nums[i] == 0 and nums[i] == target:
                    return 2
                elif nums[i] == target or -nums[i] == target:
                    return 1
                else:
                    return 0

            # recursive
            ways_add = dp(i - 1, target - nums[i])
            ways_plus = dp(i - 1, target + nums[i])
            ways = ways_add + ways_plus

            return ways

        return dp(len(nums) - 1, target)

516. Longest Palindromic Subsequence

# 首尾指针i，j相向移动
# dp方法含义：返回子串s[i..j]的最长回文子序列的长度
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        memo = [[0 for col in range(n)] for row in range(n)]

        def dp(i: int, j: int) -> int:
            # 递归出口
            if i==j and s[i]==s[j]:return 1
            elif i >= j: return 0

            # pre recursive:查memo
            if memo[i][j] != 0: return memo[i][j]

            # 递归：写memo
            if s[i] == s[j]:
                memo[i][j] = dp(i + 1, j - 1) + 2
            else:
                memo[i][j] = max(dp(i + 1, j), dp(i, j - 1))
            return memo[i][j]

        return dp(0, len(s) - 1)


def main():
    # Input: s = "bbbab"
    # Output: 4
    # Explanation: One possible longest palindromic subsequence is "bbbb".
    solution1 = Solution()
    print(solution1.longestPalindromeSubseq(s="bbbab"))

    # Input: s = "cbbd"
    # Output: 2
    # Explanation: One possible longest palindromic subsequence is "bb".
    solution2 = Solution()
    print(solution2.longestPalindromeSubseq(s="cbbd"))

    # Input "a"
    # Output 0
    # Expected 1
    solution3 = Solution()
    print(solution3.longestPalindromeSubseq(s="a"))

    # Input "aaa"
    # Output 2
    # Expected 3
    solution4 = Solution()
    print(solution4.longestPalindromeSubseq(s="aaa"))


if __name__ == '__main__':
    main()

931.minimum-falling-path-sum

from typing import List


class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        memory = dict()
        n = len(matrix)

        def dp(i: int, j: int) -> int:
            # base case
            if i == 0: return matrix[0][j]

            # pre recursive:查memory
            if memory.get((i, j)): return memory[(i, j)]

            # recursive:写memory
            if j == 0:
                memory[(i, j)] = min(
                    dp(i - 1, j) + matrix[i][j],
                    dp(i - 1, j + 1) + matrix[i][j]
                )
            elif j == n - 1:
                memory[(i, j)] = min(
                    dp(i - 1, j) + matrix[i][j],
                    dp(i - 1, j - 1) + matrix[i][j]
                )
            else:
                memory[(i, j)] = min(
                    dp(i - 1, j - 1) + matrix[i][j],
                    dp(i - 1, j) + matrix[i][j],
                    dp(i - 1, j + 1) + matrix[i][j]
                )

            # post recursive:返回memory
            return memory[(i, j)]

        # 取j从0-n中最小的那个
        min_sum = 99999999
        for j in range(n):
            # 递归部分从i=n-1减至0
            min_sum = min(min_sum, dp(n - 1, j))
        return min_sum


def main():
    # Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
    # Output: 13
    # Explanation: There are two falling paths with a minimum sum as shown.
    solution1 = Solution()
    print(solution1.minFallingPathSum(matrix=[[2, 1, 3], [6, 5, 4], [7, 8, 9]]))

    # Input: matrix = [[-19,57],[-40,-5]]
    # Output: -59
    # Explanation: The falling path with a minimum sum is shown.
    solution2 = Solution()
    print(solution2.minFallingPathSum(matrix=[[-19, 57], [-40, -5]]))


if __name__ == '__main__':
    main()

1143. Longest Common Subsequence

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        memo = [[0 for col in range(n)] for row in range(m)]

        def dp(i: int, j: int) -> int:
            # base case
            if i == -1 or j == -1: return 0

            # pre recursive：查memo
            if memo[i][j] != 0: return memo[i][j]

            # recursive
            res = 0
            if text1[i] == text2[j]:
                res = dp(i - 1, j - 1) + 1
            else:
                res = max(dp(i - 1, j), dp(i, j - 1))

            # post recursive: 写memo
            memo[i][j] = res

            return memo[i][j]

        return dp(m - 1, n - 1)


def main():
    # Input: text1 = "abcde", text2 = "ace"
    # Output: 3
    # Explanation: The longest common subsequence is "ace" and its length is 3.
    solution1 = Solution()
    print(solution1.longestCommonSubsequence(text1="abcde", text2="ace"))

    # Input: text1 = "abc", text2 = "abc"
    # Output: 3
    # Explanation: The longest common subsequence is "abc" and its length is 3.
    solution2 = Solution()
    print(solution2.longestCommonSubsequence(text1="abc", text2="abc"))

    # Input: text1 = "abc", text2 = "def"
    # Output: 0
    # Explanation: There is no such common subsequence, so the result is 0.
    solution3 = Solution()
    print(solution3.longestCommonSubsequence(text1="abc", text2="def"))


if __name__ == '__main__':
    main()