【算法】（Python）动态规划

动态规划：

• dynamic programming。"programming"指的是一种表格法，而非编写计算机程序。
• 通常解决最优化问题（optimization problem）。
• 将问题拆分成若干个子问题，求解各子问题来得到原问题的解。
• 适用于多阶段决策（以时间划分阶段的动态过程，可人为引进时间因素）。即一个活动过程可划分多个互相关联的阶段，每个阶段都需做决策，一个阶段的决策影响下一个阶段的决策，从而确定一个活动路线（即策略，每个阶段的决策组成的序列）。
• 使用条件：最优子结构（一个问题最优解包含其子问题的最优解），重叠子问题（问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题）。
• 每个子问题只计算一次，即有一个表记录每个子问题的解，再次需要该子问题时直接查表，无需重复计算。
• 两种方法：带备忘的自顶向下（递归。从整体开始，拆分多个子问题递归求解），自底向上（迭代。先解决最小问题，进而解决整体问题）。通常使用自底向上。
• 关键：解决冗余，以空间换时间（占用额外的内存，但节省计算时间）。
• 缺点：“维数障碍”（维度增加，空间复杂程度呈指数级增长），没有统一的处理方法（具体问题具体分析）。

动态规划、分治方法、贪心算法，都是将问题分成若干个子问题，求解子问题从而得到原问题的解。

动态规划与分治方法的区别：

• 动态规划的子问题相互重叠、不是独立的。分治方法的子问题互不相交、相互独立。
• 动态规划的子问题只计算一次，并保存子问题的解。分治方法会计算每次出现的子问题。若同样的问题使用分治方法，则会重复计算相同的子问题。

动态规划与贪心算法的区别：

• 动态规划寻求全局最优解（相关的子问题全部解决了，才能做出选择）。贪心算法是贪心地追求局部最优解（即当前状态下最优选择，求解选出的子问题的解），不一定全局最优解。

案例：

1、（难度：简单）【力扣】746. 使用最小花费爬楼梯

解题思路：台阶0和台阶1均可为起始点（即花费为0），此后，到达各台阶（含目的地）的最小花费：min（前1个台阶走1步到达的最小花费，前2个台阶走2步到达的最小花费）。有一个列表记录到达各台阶（含目的地）的最小累积花费。

知识点：min(a, b)：从a和b中获取最小值。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)           # 数组长度
        res = [0] * (n + 1)     # 记录到达各台阶和目的地的累积花费   
        # 从下标为0或1开始，花费为0，忽略
        # 从下标为2开始，判断前1个台阶到这和前2个台阶到这的累积最小花费，添加到结果列表中
        for i in range(2, n + 1):
            res[i] = min(res[i - 1] + cost[i - 1], res[i - 2] + cost[i - 2])
        # 返回到达目的地时的累积花费
        return res[n]

优化：各台阶（含目的地）花费涉及：前1个台阶走1步的花费，前2个台阶走2步的花费，其中最小的值。

设置3个变量：prev（当前台阶的前1个台阶，走2步到下一个需到达的台阶），curr（当前台阶，走1步到下一个需到达的台阶），next（下一个需到达的台阶）。

返回：最终到达当前台阶的累积最小花费。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)           # 数组长度
        prev, curr = 0, 0       # prev：前1个台阶，curr：当前台阶
        # 从下标为0或1开始，花费为0，忽略
        # 从下标为2开始，计算到达该台阶的累积花费
        # 当前台阶走1步到下一个台阶和前1个台阶走2步到下一个台阶的累积最小花费
        for i in range(2, n + 1):
            next = min(curr + cost[i - 1], prev + cost[i - 2])
            prev, curr = curr, next          # 向后滚动移动
        return curr

python中itertools模块中pairwise可依次生成连续的两个元素。

itertools.pairwise(可迭代对象）：返回迭代器，迭代器中为依次生成的连续的2个元素。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)           # 数组长度
        prev, curr = 0, 0       # prev：前1个台阶，curr：当前台阶
        # 从下标为0或1开始，花费为0，忽略
        # 从下标为2开始，计算到达该台阶的累积花费
        # 当前台阶走1步到下一个台阶和前1个台阶走2步到下一个台阶的累积最小花费
        import itertools
        for a, b in itertools.pairwise(cost):
            next = min(prev + a, curr + b)
            prev, curr = curr, next          # 向后滚动移动
        return curr

2、（难度：中等）【力扣】714. 买卖股票的最佳时机含手续费

解题思路：有一个二维数组，记录每一日最大收益：max（若当日手上没有股票时的最大收益，若当日手上有股票时的最大收益）。

知识点：[ [ 0,0] ] * n：二维数组，有n个元素，元素类型仍为数组。即[[0,0],[0,0],...,[0,0]]。

               二维数组[0][1]：获取二维数组的第一个元素中下标为1的值。

               max(a, b)：从a和b中获取最大值。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        # 二维数组初始化，记录[第i日手上没股票的收益,第i日手上有股票的收益]
        res = [[0, 0]] * n
        # 第1日（res列表中下标为0的元组）,下标为0的值为0（第1日手上没有股票的收益），忽略
        # 第1日（res列表中下标为0的元组）,下标为1的值为付出的买入价（第1日手上有股票的收益）
        res[0][1] = -prices[0]       
        # 遍历每日价格
        for i in range(1, n):
            # 当日,手上没有股票的收益:前1日也没股票，前1日有股票今天卖掉，取最大值
            res[i][0] = max(res[i - 1][0], res[i - 1][1] + prices[i] - fee)
            # 当日,手上有股票的收益：前1日也有股票，前1日没股票今天买入，取最大值
            res[i][1] = max(res[i - 1][1], res[i - 1][0] - prices[i])
        # 最后，手上没有股票收益更大
        return res[n - 1][0]

优化：今日收益涉及前1日手上是否有股票。滚动记录。

设置2个变量：zero（当日若手上没有股票时的收益）。one（当日若手上有股票时的收益）。

返回最终手上没有股票时的收益。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        # 第1日，zero:手上没有股票的收益，one:手上有股票的收益(付出的买入价)
        zero, one = 0, -prices[0]
        # 遍历每日价格
        for i in (range(1, n)):
            # 当日，手上没有股票的收益：前1日也没股票，前1日有股票今天卖掉，取最大值
            zero = max(zero, one + prices[i] - fee)
            # 当日，手上有股票的收益：前1日也有股票，前1日没有股票今天买入，取最大值
            one = max(one, zero - prices[i])
        # 最后，手上没有股票，收益最大
        return zero

 注：本题其他解题方法：贪心算法

3、（难度：困难）【力扣】871. 最低加油次数

解题思路：遍历每个加油站，先假设每到一个加油站都加油，i个加油站最多加油 i 次。

要求加油次数尽可能少，为避免重复加油，依次减少到达该加油站的加油次数（j从i到0），滚动调整加油 j 次后可行驶最大距离：max（已加油 j次 在本加油站不加油的最大距离，已加油 j-1次 在本加油站加油后最大距离）。

最后遍历加油 j次后可行驶的最大距离，大于等于目的地的距离，则返回下标即加了几次油，否则无法到达目的地返回-1。

知识点：enumerate(可迭代对象)：返回所有的元素下标和元素内容，元组形式。一般用于for循环。

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:       
        res = [0] * (len(stations) + 1)     # 记录每次加油后（含初始油量）可以行使的最大距离      
        res[0] = startFuel                  # 初始油量可以行使的最大距离
        # 遍历每个加油站
        for i, (long, fuel) in enumerate(stations):
            # 先假设每到一个加油站就加油,再减少到这的加油次数,滚动调整加油j次(i到0)后可行使的最大距离
            # 例如到达第3个加油站后最多加油3次：
            # 若加油3次最大行驶距离：max(已加油3次本次不加油最大距离, 已加油2次本次再加油后最大距离)
            # 若加油2次最大行驶距离：max(已加油2次本次不加油最大距离, 已加油1次本次再加油后最大距离)
            # 若加油1次最大行驶距离：max(已加油1次本次不加油最大距离, 已加油0次本次再加油后最大距离)            
            for j in range(i, -1, -1):      # 倒序，避免重复加油
                # 到达加油站后，才判断在这是否加油，以及加油j次后可行驶最大距离
                if res[j] >= long:
                    res[j + 1] = max(res[j + 1], res[j] + fuel)
        # 遍历加油j次后的最大行使距离，超过目的地则返回下标即加了几次油
        for j, val in enumerate(res):
            if val >= target: return j
        return -1

注：本题其他解题方法：贪心算法