LeetCode刷题——动态规划（python语言）

一、动态规划

1.1 基本概念

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

1.2 算法步骤

1.确认状态，一般是问题要求解的核心内容，而且可以分为若干子问题。
2.确定状态转移方程，列举出一个状态到另一个状态的变化量，通常要的分情况讨论。
3.确定初始值，确定初始状态的值，一般取特殊值或数组第一个值。
4.顺序，动态规划是按照何种顺序进行的。

二、刷题

2.1 最大子数组和

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

子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
**解法:**根据动态规划的基本思想确定状态和状态转换方程，初始值和顺序。主要是对于opt进行更新

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        opt = [nums[0] if nums else None]
        for i in nums[1:]:
            opt.append(max(opt[-1]+i,i))
        return max(opt)

2.2 最长公共子序列

定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

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

示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
**解法：**根据动态规划思想，设置二维矩阵，针对两个字符串分别遍历，相等加1，否则i-1或者j-1取最大值。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1,len2 = len(text1),len(text2)
        opt = [[0 for i in range(len2+1)] for i in range(len1+1)]
        for i in range(len1):
            for j in range(len2):
                if(text1[i]==text2[j]):
                    opt[i+1][j+1] = opt[i][j] + 1 
                else:
                    opt[i+1][j+1] = max(opt[i+1][j],opt[i][j+1])
        return opt[len1][len2]

2.3 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成
**解法一：**将字符串反转，问题转化为，两个字符串的最长公共子序列

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        #动态规划四个步骤,将字符串反转，判断最长公共子序列，即最长回文子序列
        #1.确状状态:opt[j]存储[0:j]即最长回文子序列
        #2.确定状态转移方程:t[i]==t[j]匹配+1，否则返回i-1或者j-1的最大值
        #3.初始条件opt[0][0]=0即为空字符串，结束条件，字符串遍历完毕。
        #4.顺序，i从1到n，j从1到n。记得opt为[n+1][n+1]
        n = len(s)
        opt = [[0 for i in range(n+1)] for i in range(n+1)]
        ss = s[::-1]
        for i in range(n):
            for j in range(n):
                if(s[i]==ss[j]):
                    opt[i+1][j+1] = opt[i][j] + 1 
                else:
                    opt[i+1][j+1] = max(opt[i+1][j],opt[i][j+1])
        return opt[n][n]

**解法二：**根据回文的规律。利用动态规划的思想

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # 动态规划的四要素
        # 第一步：确认状态
        # dp[i][j]表示s字符的第i个字符到第j个字符组成的字符串中，最长回文序列是多少；
        # 第二步：转移方程
        # 如果s的第i个字符和第j个字符相同的话,s[i]=s[j]
        # dp[i][j] = df[i+1][j-1]
        # 如果 s[i] != s[j]
        # dp[i][j] = max(dp[i+1][j],dp[i][j-1]),选取其中最长的一个（不用考虑啥时候删除，因为当两边不相等的时候已经相当于把其过滤掉了）
        # 第三步：初始化
        # dp[i][j] = 1 ,单字符
        # 第四步：顺序
        # i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了。
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            dp[i][i] = 1
            for j in range(i+1,n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1]+2
                else:
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])

        return dp[0][n-1]            

2.4 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
**解法：**根据动态规划的思想不断更新前i天的最小值，根据第i天的价格更近最大收益。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #动态规划
        #1.确认状态:前i天的最小值（第i天的价格减去前i天的最小值为第i天最大收益）
        #2.确认状态转移方程：第i+1天的价格减去前i天的最小值。更新最小值
        #3.初始条件，最大收益为0，第一天最小值为prices[0].
        #4.顺序，按照时间遍历
        M = 0 
        opt = [prices[0] if prices else None]
        for i in prices[1:]:
            opt.append(min(opt[-1],i))
            M = max(M,i-opt[-1])
        return M
            

2.5 买卖股票的最佳时机 II

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
**解法：**利用动态规划的思想，计算本质。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #每天尝试都,这里说明一个问题，一天卖掉昨天，卖今天的，虽然不符合问题，但收益相同
        #1.确认状态，前i天的最大收益
        #2.确认状态转移方程，更新i+1天的最大收益，更新最小值
        #3.初始状态确定，第0天最大值为0
        #4.顺序，按照时间确定
        opt = [0]
        for i in range(1,len(prices)):
            opt.append(max(opt[-1]+prices[i]-prices[i-1],opt[-1]))
        return opt[-1]