动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

1143. 最长公共子序列

最长公共子序列（Longest Common Subsequence，简称 LCS)

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-subsequence

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

def longestCommonSubsequence(s1: str, s2: str) -> int:
    m = len(s1)
    n = len(s2)
    dp = [[0] * (n+1) for i in range(m+1)]
    # // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
    # // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
    # // base case: dp[0][..] = dp[..][0] = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            # // 现在 i 和 j 从 1 开始，所以要减一
            if s1[i-1] == s2[j-1]:
                #  // s1[i-1] 和 s2[j-1] 必然在 lcs 中
                dp[i][j] = 1+dp[i-1][j-1]
            else:
                # s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
                # 还有一种dp[i-1][j-1]包含在下面两种中，所以可忽略。
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

def maxSubArray(self, nums: List[int]) -> int:
        dp = [0 for i in range(len(nums))]
        dp[0] = nums[0]
        # 以nums[i]为结尾的「最大子数组和」为dp[i]。
        for i in range(len(nums[1:])):
            dp[i+1] = max(dp[i]+nums[i+1], nums[i+1])
        return max(dp)