动态规划

动态规划中的子问题往往不是相互独立的,子问题是重叠的，在求解的过程中，许多子问题的解被反复的使用。为了避免重复计算，动态规划算法使用填表来保存子问题解的方法。

适合动态规划来解决的问题具有三个特点：最优化原理、无后效性、有重叠子问题。

1、 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
2、 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
3、 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。)

使用动态规划做题时需要考虑：

  1. 状态的定义
  2. 状态如何转移，状态转移方程 [大问题的最优解如何由小问题的最优解得到。]
  3. 初始化
  4. 结果的输出
  5. 优化空间

python涉及的知识点

状态矩阵初始化：

dp = [[False] * n for _ in range(n)]

相关练习

LeetCode中相关的题目：

题目详细描述

最长回文子串：这个题目可以使用动态规划、中心扩散、Manacher算法，其中动态规划和中心扩散必须掌握，动态规划和中心扩散的复杂度一样，但是空间复杂度不同，且中心扩散的效果好。
1、动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2: ## 只有一个字符的时候，本身就是最长回文子串
            return s 
        ## 确定状态：是否是回文子串
        dp = [[False] * n for _ in range(n)] ## 初始化不能写错，
        res = ""

        for leng in range(n): ## 枚举子串的长度
            for i in range(n): ## 枚举子串的初始位置i，那么子串的结束位置就是i+leng
                j = i + leng
                if j >= n: ## 当无法获取这个长度的子串则结束
                    break
                if leng == 0: ## 初始化动态规划表的对角线
                    dp[i][j] = True
                elif leng == 1: ## 只有两个元素时，只要两者相同就是回文串
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i+1][j-1] and s[i] == s[j]) ## 状态转移
                if dp[i][j] and leng + 1 > len(res): 
                ## 当是回文串，且已经字符串最长的时候，那么这个子串先被认定为最长回文子串
                    res = s[i:j+1] ## i是初始位置，j+1是结束位置
        return res

2、中心扩散

class Solution:
    def expandAround(self,s,left,right): ## 前后指针来判断回文串的开始截止位置
            ## 没有到边界并且左右字符相同，则继续像两遍扩散
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1 ## 向左
                right += 1 ## 向右
            ## 因为遍历到不同的元素的上一步已经+-1，所以这里需要再-+1获取正确的位置
            return left+1 ,right-1 

    def longestPalindrome(self, s: str) -> str:
        start, end = 0,0 ## 记录开始、结束位置
        n = len(s)
        for i in range(n):
            left1,right1 = self.expandAround(s,i,i) ## 奇数
            left2,right2 = self.expandAround(s,i,i+1) ## 偶数
            if right1 - left1 > end - start: ## 当找到比当前的回文子串要长，则更新
                start,end = left1,right1
            if right2 - left2 > end - start: ## 当找到比当前的回文子串要长，则更新
                start,end = left2,right2
        return s[start:end+1]

3、Manacher算法

class Solution:
    # Manacher 算法
    def longestPalindrome(self, s: str) -> str:
        # 特判
        size = len(s)
        if size < 2:
            return s

        # 得到预处理字符串
        t = "#"
        for i in range(size):
            t += s[i]
            t += "#"
        ## 或者可以简写为 t = '#' + '#'.join(list(s)) + '#'
        # 新字符串的长度
        t_len = 2 * size + 1

        # 数组 p 记录了扫描过的回文子串的信息
        p = [0 for _ in range(t_len)]

        # 双指针，它们是一一对应的，须同时更新
        max_right = 0
        center = 0

        # 当前遍历的中心最大扩散步数，其值等于原始字符串的最长回文子串的长度
        max_len = 1
        # 原始字符串的最长回文子串的起始位置，与 max_len 必须同时更新
        start = 1

        for i in range(t_len):
            if i < max_right:
                mirror = 2 * center - i
                # 这一行代码是 Manacher 算法的关键所在，要结合图形来理解
                p[i] = min(max_right - i, p[mirror])

            # 下一次尝试扩散的左右起点，能扩散的步数直接加到 p[i] 中
            left = i - (1 + p[i])
            right = i + (1 + p[i])

            # left >= 0 and right < t_len 保证不越界
            # t[left] == t[right] 表示可以扩散 1 次
            while left >= 0 and right < t_len and t[left] == t[right]:
                p[i] += 1
                left -= 1
                right += 1

            # 根据 max_right 的定义，它是遍历过的 i 的 i + p[i] 的最大者
            # 如果 max_right 的值越大，进入上面 i < max_right 的判断的可能性就越大，这样就可以重复利用之前判断过的回文信息了
            if i + p[i] > max_right:
                # max_right 和 center 需要同时更新
                max_right = i + p[i]
                center = i

            if p[i] > max_len:
                # 记录最长回文子串的长度和相应它在原始字符串中的起点
                max_len = p[i]
                start = (i - max_len) // 2
        return s[start: start + max_len]

回文子串
1、动态规划

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = ""
        n = len(s)
        if n < 2:
            return 1
        dp = [[False]*n for _ in range(n)]
        count = 0

        for leng in range(n):
            for i in range(n):
                j = i + leng
                if j >= n:
                    break
                if leng == 0:
                    dp[i][j] = True
                elif leng == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i+1][j-1] and s[i] == s[j])
                
                if dp[i][j]:
                    count += 1
        return count

2、中心扩散

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        if n < 2:
            return 1
        self.count = 0
        def midexpand(left,right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                self.count += 1
        for i in range(n):
            midexpand(i,i)
            midexpand(i,i+1)
        return self.count

3、Manacher算法



最大子序和：
1、动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]      
        pre = 0
        maxL = nums[0]
        for item in nums:
            pre = max(item+pre,item)
            maxL = max(maxL,pre)       
        return maxL

121. 买卖股票的最佳时机
O(n) O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        minprice = 1e5  ## 初始化最小的价格
        maxprofit = 0  ## 初始化最大利润，设为为0

        for price in prices:
            if price < minprice:
                minprice = price
            if price - minprice > maxprofit:
                maxprofit = price - minprice
        
        return maxprofit

O(n) O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minprice = 1e5
        maxprofit = 0
        for price in prices:
            minprice = min(minprice,price)  ## 更新最低点
            maxprofit = max(maxprofit,price - minprice) ## 求差值，更新最大差值
            
        return maxprofit
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0: return 0 # 边界条件
        dp = [0] * n
        minprice = prices[0] 

        for i in range(1, n):
            minprice = min(minprice, prices[i]) ## 最小价格
            ## 当天的最大利润，是昨天的最大利润或者当天价格减去最小值的值
            dp[i] = max(dp[i - 1], prices[i] - minprice)

        return dp[-1]