2 动态规划复习

2.1 动规基本原理

动态规划DP是针对一类求最优解问题的算法，其核心是将一个问题分解成为若干个子问题。通过求每一次的最优决策，来得到一个最优解。另一种理解方式是DP的核心是加法原理（下文的人人为我型递归）和乘法原理（下文的我为人人型递归）。通过这两个原理， 在当状态的前有限多个状态中找到最优解来求得当前状态， 而对于前一个或者前几个状态采用同样的方法知道求出边界状态。
在学会搜索之后， 最简单入门DP的方法就是记忆化搜索。但是后来会发现大多数DP题目因为时间和内存的限制并不能使用递归（函数的递归调用会占用栈内存， 另外函数的递归调用也将占用大量的时间）。

一般而言，只要所求解的问题可以划分成若干个子问题，并且原问题的最优解包含子问题的最优解，就可以用动态规划来求解。动态规划的基本思想是分治，要注意去冗余，求解子问题的最优解并保存下来，不要重复计算。一般解决步骤是自底向上的步骤，与记忆化搜索（自顶向下）相反。找出原问题和子问题的递推关系，指定好递归边界，通过求解子问题的最优解来得到全局最优。

2.2 动规解题思路

• 状态定义
• 状态转移方程
• 初始化
• 返回值

2.3 动规适合题型

求最值的问题，如（字符串最大和，数组最大和，最长公共子序列）【核心：穷举—可能需要递归】
方法种数

---

* 实战例题

剑指 Offer 10- I. 斐波那契数列

斐波那契数列是一个非常典型的递归问题。我们可以直接用代码编码出以下三句，包括递归边界和递归递推表达式即可，然而这样计算会有很多计算重复，造成冗余计算。
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
如，计算F(8) = F(7)+F(6) = F(6)+F(5)+F(5)+F(4)=F(5)+F(4)+F(4)+F(3)+F(4)+F(3)+F(3)+F(2) = 。。。
可以看出F(6)~F(1)都冗余计算了，我们的解决办法是设置一个数组，对每一个值进行存储

[x] 递归法：
原理： 把f(n) 问题的计算拆分成f(n−1) 和f(n−2) 两个子问题的计算，并递归，以f(0) 和f(1) 为终止条件。
缺点： 大量重复的递归计算，例如f(n) 和 f(n - 1)两者向下递归需要 各自计算 f(n−2) 的值。
记忆化递归法：
原理： 在递归法的基础上，新建一个长度为n 的数组，用于在递归时存储f(0) 至f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。
缺点： 记忆化存储需要使用 O(N)的额外空间。
动态规划：
原理： 以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)为转移方程。
从计算效率、空间复杂度上看，动态规划是本题的最佳解法。
求余运算规则： 设正整数 x, y, px,y,p ，求余符号为⊙ ，则有p(x+y)⊙p=(x⊙p+y⊙p)⊙p
由于 Python 中整形数字的大小限制取决计算机的内存（可理解为无限大），因此也可不考虑大数越界问题；但当数字很大时，加法运算的效率也会降低，因此不推荐此方法。

class Solution:
    def fib(self, n: int) -> int:
        # 动态规划
        dp = list(range(1000000)) # 需要初始化dp数组
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n+1):  # n表示求和次数
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
        return dp[n]

from functools import lru_cache
class Solution:
    @lru_cache(None) # 一种缓存清理工具
    def fib(self, n: int) -> int:
        if n<2:
            return n
        return (self.fib(n-1)+self.fib(n-2))%1000000007

class Solution:
    def fib(self, n: int) -> int:
        if n<=1:
            return n
        # 循环两数之和
        a = 0
        b = 1
        for i in range(n-1): # n表示求和次数
            tmp = (a+b)%1000000007
            a = b
            b = tmp 
        return b

剑指 Offer 10- II. 青蛙跳台阶问题

最后一步可以分为两种情况。对于计算方法数的类似题目可以参照该思路。

class Solution:
    def numWays(self, n: int) -> int:
        # 思想等同于斐波那契数列，
        if n <=1:
            return 1
        a = 1
        b = 1
        for i in range(n-1):
            fn = (a+b)%1000000007
            a = b 
            b = fn
        return b

剑指 Offer 19. 正则表达式匹配

看完规则，第一反应是遍历整个字符串。如果遇到点，那么对应任意字符都可以。如果遇到星号，对应的指针向前移动查看是否与字符串2星号前字母一致。
动规的思想是：想要判断两个字符串是否匹配，拆分成子问题就是，判断子串是否匹配

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s) + 1, len(p) + 1
        dp = [[False] * n for _ in range(m)]
        dp[0][0] = True  # s和p都是空字符是为true
        # 初始化首行(s='')，如果星号在偶数列(从1计数，j从0计数)，那么星号和前面一个字符的组合就可有可无了（如a*，可以匹配空字符或者无限多个a）
        for j in range(2, n, 2):  # 若p是"a*"成对出现的，那么星号所处位置都与此时的s匹配
            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
        # 状态转移
        for i in range(1, m):  # 扫描s和p的每一个字符，相当于给子串逐个添加一个字符，并计算状态
            for j in range(1, n):
                if p[j - 1] == '*':  # 当前是*，就需要比较p的前一字符（下标为j-2）
                    if dp[i][j - 2]:  # 表示(p[j-2]*)出现了0次
                        dp[i][j] = True  # 1.
                    elif dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'):  #
                        dp[i][j] = True  # pj出现了*，那么需要比较的就是上一层的子串状态了
                else:
                    if dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.'):
                        dp[i][j] = True  # 当前字符一致or当前p是百变字符
        return dp[-1][-1]


ss = Solution()
s = "bab"
p = "bc*a*b"
print(ss.isMatch(s, p))

# DP在于问题的拆分，并且原问题求解包括一步一步的子问题求解，即可以用状态转移方程表示，其实就是递归的过程。
# 然而递归的时间复杂度太高，因此用DP的方式相当于将子问题状态值保存下来。
# 那么，首先要做的就是状态的假设与问题的拆分
# 对于多个步骤完成的任务，我们可以考察最后一步的可能情况（青蛙问题），假设f(n)表示第n次的种数，类比斐波那契数列来求解。
# 对于字符串匹配问题，我们可以假设f(i,j)表示i和j能否匹配

# 其次，定义初始状态值
# 最后，定界

剑指 Offer 42. 连续子数组的最大和

# https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59gq9c/
class Solution:
    def maxSubArray(self, nums) -> int:
        """
        要想得到整个list中和最大的子串，用动规的思路，先求初始子串的和，然后添加一个元素，判断是否和的变化情况
        无论如何，至少得遍历一遍整个list,时间复杂度至少为O(n)，空间至少为O(1)
        如何拆解该问题：
        按照DP的解题思路dp[i]的下标应该随着添加一个元素而增加，因此用i表示list中num的下标，
        因此dp[i]表示以nums[i]元素为结尾的子串的最大和
        逐个遍历list，如果dp[i-1]>0,则dp[i] = dp[i-1]+nums[i]；否则，dp[i]=nums[i]
        ，即dp[i]=max(dp[i-1],0)+nums[i]。最后输出max(dp)
        最后代码，直接在nums上修改，用nums代替dp
        """
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)


aa = Solution()
print(aa.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 求和问题可以看作：每一次在上一次的基础上再添加一个元素，
# 因此使用动态规划的思想，就是从头开始计算，然后根据题目要求判断，并添加一个元素。
# 本题就是要求和最大的子串，其实还是从第一个元素开始遍历，逐个累加新元素得到新的和。
# 所有动规的题目不同之处便在于判断的条件和递推式子。
# 相似的是都可以都可以拆解为从头开始，然后逐个添加元素的过程。
# 边添加元素，边判断
# 解题步骤：
# 1.确定子问题：dp[i]表示以nums[i]元素为结尾的子串的最大和
# 2.状态转移：dp[i]=max(dp[i-1],0)+nums[i]
# 3.设计dp数组，避免重复计算：本题直接可以在nums本身修改，空间复杂度为O(1)且没有重复计算。如果不用本身，则开辟dp数组会增加空间复杂度；或者可以考虑用指针变量来保存一些值，毕竟中间值是不需要最后输出的
# 4.整合思路，设计代码

剑指 Offer 46. 把数字翻译成字符串

"""
# https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/99wd55/
# 按照数字和字母的映射对，如0-25分别对应a-z，对题目给定的整数进行翻译。
# 本题的问题是求解可能的种类数（和“青蛙跳一阶两阶一共多少种跳法”类似）
# 那么，本题的潜在意思是，一位数可以对应a-j,两位数对应k-z，那么有多少种对应方法？
# 其中，比青蛙题多的一个条件是，又是不可以跳两步，因为两位数可能大于25.
# 状态定义：用dp[n]表示n位数字的翻译总数，那么翻译为最后一个字母可能有两种情况，分别是最后两个数字和最后一个数字，用dp[n-1]和dp[n-2]表示。
# 状态转移：dp[n]=dp[n-1]+dp[n-2]
# 初始化状态：dp[0]=1,dp[1]=1,如果nums[i-1]和nums[i]组成的十位数大于25，则不加；否则可使用以上转移公式
class Solution:
    def translateNum(self, num: int) -> int:
        # 将数字转为list
        nums = [int(i) for i in str(num)]
        if len(nums) < 2:
            return 1
        dp = [0] * (len(nums) + 1)
        dp[0], dp[1] = 1, 1
        for i in range(2, len(dp)):
            if nums[i - 2] * 10 + nums[i - 1] > 25 or nums[i - 2] * 10 + nums[i - 1] < 10:
                dp[i] = dp[i - 1]
            else:
                dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]
# 自己的青蛙解法忽略掉的点：
# 1.一位数边界未设置导致一位数结果为2
# 2.当出现09这种组合时，满足<=25,但是等同于9，因此需要补充小于10的条件
"""

# 改进，
# 1.不重复计算,用变量取代dp数组
# 2.直接用字符串操作，不需要转成数字
# 3.由于 Python 语言特性，可不使用临时变量
class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a, b = 1, 1
        for i in range(2, len(s) + 1):
            # tmp = a + b if '10' <= s[i - 2:i] <= '25' else b
            # a = b
            # b = tmp
            b, a = a + b if '10' <= s[i - 2:i] <= '25' else b, b
        return b

# 然而，我的第一种dp方法在执行上秒杀改进后的：
# 执行用时：32 ms, 在所有 Python3 提交中击败了93.64%的用户
# 内存消耗：14.8 MB, 在所有 Python3 提交中击败了58.07%的用户

ss = Solution()
print(ss.translateNum(2012))

剑指 Offer 47.礼物的最大价值

# 给定一个m*n的棋盘，从左上角开始拿东西，每次走一步只能右边或下边，直到右下角，要求路线的最大价值。
# 状态定义：dp[i][j]表示走到grid[i][j]时的最大值
# 状态转移：左侧和上边的最大值加上当前元素。dp[i][j] = max(dp[i-1,j],dp[i,j-1]) + grid[i][j]
# 状态初始化:不需要初始化,定义的时候已经将dp所有值为0了
#   dp的行列数需要比grid大于1，表示上一个状态为0.也可以用某个变量标记一下0
class Solution:
    def maxValue(self, grid) -> int:
        m, n = len(grid) + 1, len(grid[0]) + 1
        dp = [[0] * n] * m
        print(dp)

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
                # todo 为什么这里改变了一整列的值，而不是坐标对应的那一个位置的值？
                print(dp)

        return dp[-1][-1]


# 改进，用grid代替dp，需要初始化左侧一列和上边一行为0
class Solution1:
    def maxValue(self, grid) -> int:
        m, n = len(grid), len(grid[0])
        for j in range(1, n):  # 初始化第一行，max(左，上)=左，因为第一行上=0
            grid[0][j] += grid[0][j - 1]
        for i in range(1, m):  # 初始化第一列，max(左，上)=上，因为第一列左=0
            grid[i][0] += grid[i - 1][0]

        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1])

        return grid[-1][-1]


ss = Solution()
# print(ss.maxValue([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
print(ss.maxValue([[1, 3, 1], [1, 5, 1]]))

剑指 Offer 48. 最长不含重复字符的子字符串

# 题目分析：
# 长度为n的字符串共有n(n+1)/2个子字符串（复杂度为O(n^2)
# 判断长度为n的字符串是否有重复字符的复杂度为O(n)
# 因此本题使用暴力法解决的复杂度为O(n^3)
#
# 状态定义：dp[i]表示以str[i]结尾的最长不重复子串的个数
# 状态转移：添加新字符，dp[]
# 状态初始化：dp[0]=1
# 是否包含重复字符如何判断?选择使用两个下标变量表示
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dp, j = [1] + [0] * (len(s) - 1), 0  # 用于比较i之前的元素是否与i所指元素一致
        if s == '':
            return 0
        for i in range(1, len(s)):
            # 每新加一个字符，就需要判断该字符是否在s[j:i]中包含，若不包含j不变，若包含j,那么j移动到下一个字符
            for k in range(j, i):
                if s[i] == s[k]: j = k + 1
            dp[i] = i - j + 1
            print(i, j, dp)
        return max(dp)


# 虽然解出来了，但是没有找到状态转移公式：dp[i]=dp[i-1]+1 if dp[i-1]<j-i else i-j
# 并且时间复杂度为O(n^2)
print(Solution().lengthOfLongestSubstring('abcabcbb'))

剑指 Offer 49. 丑数

# 根据丑数的定义（其因子只包含235，1为特殊的丑数），丑数应该是另一个丑数乘以 2、3 或者 5 的结果
# 创建数组，逐个计算出从小到大的丑数
# 状态定义：dp[n]表示第n+1个丑数
# dp[0]=1 (a,b,c=0)
# dp[1]=min(dp[0]*[2,3,5])=2
# dp[2]=min(dp[0]*[2,3,5],dp[1]*[2,3,5])=3(此处的dp[0]*2已经填充过了，不能在这里比较了，因此考虑到可能需要为235分别设置一个指针)
# ...

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp, a, b, c = [1] * n, 0, 0, 0
        for i in range(1, n):
            na, nb, nc = dp[a] * 2, dp[b] * 3, dp[c] * 5  # 用之前已知的丑数乘以235
            dp[i] = min(na, nb, nc)  # 要保证丑数从小到大的顺序
            # 控制已知丑数下标
            if dp[i] == na: a += 1
            if dp[i] == nb: b += 1
            if dp[i] == nc: c += 1
        return dp[n - 1]

print(Solution().nthUglyNumber(10))

剑指 Offer 63. 股票的最大利润

# 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
# 给定一个list,买入的index要在卖出的index之前，且prices[卖出]>prices[买入]
# 按照常规的DP思路：
# 1.状态定义：假设dp[i]表示第i天卖出时的最大利润。
# 2.状态转移：dp[i] = prices[i]-min(prices[:i])
# 3.状态初始化：dp[0]=0
# 4.简化dp,用a直接存储当前max收益
# class Solution:
#     def maxProfit(self, prices) -> int:
#         a = 0
#         for i in range(1, len(prices)):
#             a = max(a, prices[i] - min(prices[:i]))
#         return a
# 执行耗时1千多ms

# 改进，求历史买入最低价钱的时候用cost存储了一下，在min这里减少了计算时间
class Solution:
    def maxProfit(self, prices) -> int:
        cost, profit = float("+inf"), 0
        for price in prices:
            cost = min(cost, price)
            profit = max(profit, price - cost)
            print(cost, price,profit)
        return profit

ss = Solution()
print(ss.maxProfit([7, 1, 5, 3, 6, 4]))