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

---

---

Statement ：
The algorithm is based on https://labuladong.github.io/
python Language implementation

---

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: check memory
            if memory.get((i, j)): return memory[(i, j)]

            # recursive： Result write memory
            # 1. The pointer i,j When the indicated characters are equal ：
            # i,j All move forward one bit , Operands （insert,delete,replace） unchanged 
            if word1[i] == word2[j]:
                memory[(i, j)] = dp(i - 1, j - 1)
            # 2. The pointer i,j When the indicated characters are not equal ：
            #  Operands plus one , The pointer moves bits according to the specific operation 
            # 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： return 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

"""  This example contains repeated subproblems , Use memo to optimize , Here's why ： 【 Just abstract out the recursive framework , Check whether the path between different state transitions is unique 】： only , There is no overlapping subproblem , No memo required   Is not the only , There are overlapping sub problems , It is necessary to use the memo to remove the duplicate   The recursive framework of this problem is ： def dp(i: int, target: int) -> int: dp(i - 1, target - nums[i]) dp(i - 1, target + nums[i])  If nums[i] = 0, So there are two 「 state 」 Exactly the same recursive function , There is no doubt that such recursive computation is repeated .  This is the overlapping subproblem , And as long as we can find an overlapping subproblem , There must be many overlapping subproblems .  therefore , state  (i, remain)  It can be optimized with memo skills ： ！！！ use Python Of 【 Hashtable dict】 To make a memo , among dict Of 【key by dp Method a tuple pair composed of all input parameters ：(dp_arg1, dp_arg2, ...), That is, the combination of all variable states 】 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: check memory
            # NOTE: Need to put i and target As a combination of key, Instead of just i As key
            # ！！！ I need to put dp The combination of all mutable states contained in the method acts as key！！！
            if memory.get((i,target)): return memory[(i,target)]

            # recursive: Write 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

#  Head and tail pointer i,j Move in the opposite direction 
# dp Meaning of method ： Returns the substring s[i..j] The length of the longest palindrome subsequence of 
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:
            #  Recursive export 
            if i==j and s[i]==s[j]:return 1
            elif i >= j: return 0

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

            #  recursive ： Write 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: check memory
            if memory.get((i, j)): return memory[(i, j)]

            # recursive: Write 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: return memory
            return memory[(i, j)]

        #  take j from 0-n The smallest one 
        min_sum = 99999999
        for j in range(n):
            #  Recursive part from i=n-1 Be reduced to 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： check 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:  Write 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()

---

---

10.regular-expression-matching

---

---