动态规划

2021-07-03 |本文 6028 字| 需要时间: 18 分钟| <--阅读量: -->

目录：

一、简介
- 1.1 背景
- 1.2 思考过程（示例）
- 1.3 DP与其他算法的关系
二、线性动态规划
- 2.1 单串问题
  - 2.1.1 LIS系列
  - 2.1.2 最大子数组和系列
  - 2.1.3 打家劫舍系列
  - 2.1.4 变形，需要两个位置的情况: dp[i][j] 以 j, i 结尾
  - 2.1.5 与其他算法配合
  - 2.1.6 其他
  - 2.1.7 带维度单串
    - 最大平均值和的分组 —— k 是个数
    - 鸡蛋掉落 —— k 是次数，k 上有二分
    - 粉刷房子 —— k 是颜色
    - 粉刷房子 II —— k 是颜色
    - 奇偶跳 —— k 表示当前的奇偶状态
    - 青蛙过河 —— k 表示上一步的跳的步数
    - 安排邮筒 —— k 是个数，前缀和维护状态转移时的查询
    - 抛掷硬币 —— k 是个数
    - 分割数组的最大值 —— k 是份数
    - 给房子涂色 III —— 有两个指标 k 颜色；t 街区数
  - 2.1.8 股票系列
    - 买卖股票的最佳时机
    - 买卖股票的最佳时机 II
    - 买卖股票的最佳时机 III
    - 买卖股票的最佳时机 IV
    - 最佳买卖股票时机含冷冻期
    - 买卖股票的最佳时机含手续费
- 2.2 双串问题
  - 2.2.1 LCS 系列
  - 2.2.2 字符串匹配系列
  - 2.2.3 其他
  - 2.2.4 带维度双串
- 2.3 矩阵问题
  - 2.3.1 矩阵dp[i][j]
  - 2.3.2 矩阵dp[i][j][k]
- 2.4 无串线性问题
三、前缀和
四、区间动态规划
- 4.1 简介
- 4.2 经典问题
- 4.3 回文问题
  - 最长回文子串
  - 回文子串
  - 最长回文子序列
  - 段式回文
  - 统计不同回文子字符串
  - 让字符串成为回文串的最少插入次数 —— 最长回文子序列
- 4.4 其他

一、简介

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。

使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

1.1 背景

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划不是某一种具体的算法，而是一种算法思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
应用这种算法思想解决问题的可行性，对子问题与原问题的关系，以及子问题之间的关系这两方面有一些要求，它们分别对应了最优子结构和重复子问题。

最优子结构

最优子结构规定的是子问题与原问题的关系

动态规划要解决的都是一些问题的最优解，即从很多解决问题的方案中找到最优的一个。当我们在求一个问题最优解的时候，如果可以把这个问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得出最终的结果。总结来说就是一个问题的最优解是由它的各个子问题的最优解决定的。

将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键。在解题中一般用状态转移方程描述这种组合。例如原问题的解为 f(n)f(n)，其中 f(n)f(n) 也叫状态。状态转移方程 f(n) = f(n - 1) + f(n - 2)f(n)=f(n−1)+f(n−2) 描述了一种原问题与子问题的组合关系。在原问题上有一些选择，不同选择可能对应不同的子问题或者不同的组合方式。

找到了最优子结构，也就能推导出一个状态转移方程 f(n)f(n)，通过这个状态转移方程，我们能很快的写出问题的递归实现方法。

重复子问题

重复子问题规定的是子问题与子问题的关系。

当我们在递归地寻找每个子问题的最优解的时候，有可能会重复地遇到一些更小的子问题，而且这些子问题会重叠地出现在子问题里，出现这样的情况，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。

重复子问题不是保证解的正确性必须的，但是如果递归求解子问题时，没有出现重复子问题，则没有必要用动态规划，直接普通的递归就可以了。

例如，斐波那契问题的状态转移方程 f(n) = f(n - 1) + f(n - 2)f(n)=f(n−1)+f(n−2)。在求 f(5)f(5) 时，需要先求子问题 f(4)f(4) 和 f(3)f(3)，得到结果后再组合成原问题 f(5)f(5) 的解。递归地求 f(4)f(4) 时，又要先求子问题 f(3)f(3) 和 f(2)f(2) ，这里的 f(3)f(3) 与求 f(5)f(5) 时的子问题重复了。

解决动态规划问题的核心：找出子问题及其子问题与原问题的关系

找到了子问题以及子问题与原问题的关系，就可以递归地求解子问题了。但重叠的子问题使得直接递归会有很多重复计算，于是就想到记忆化递归法：若能事先确定子问题的范围就可以建表存储子问题的答案。

动态规划算法中关于最优子结构和重复子问题的理解的关键点：

证明问题的方案中包含一种选择，选择之后留下一个或多个子问题
设计子问题的递归描述方式
证明对原问题的最优解包括了对所有子问题的最优解
证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）

1.2 解决DP的思考过程

举个例子

题目：300.最长上升子序列
描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例：
```
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是4。
```
考虑能否将问题规模缩小

将问题规模减小的方式有很多种，一些典型的减小方式是动态规划分类的依据，例如线性，区间，树形等。这里考虑数组上常用的两种思路：
每次减少一半：如果每次将问题规模减少一半，原问题有[10,9,2,5]，和[3,7,101,18]，两个子问题的最优解分别为 [2,5] 和 [3,7,101]，但是找不到好的组合方式将两个子问题最优解组合为原问题最优解 [2,5,7,101]。
每次减少一个：记 f(n)f(n) 为以第 nn 个数结尾的最长子序列，每次减少一个，将原问题分为 f(n-1)f(n−1), f(n-2)f(n−2), …, f(1)f(1)，共 n - 1n−1 个子问题。n - 1 = 7n−1=7 个子问题以及答案如下：

[10, 9, 2, 5, 3, 7, 101] -> [2, 5, 7, 101]
[10, 9, 2, 5, 3, 7] -> [2, 5, 7]
[10, 9, 2, 5, 3] -> [2, 3]
[10, 9, 2, 5] -> [2, 5]
[10, 9, 2] -> [2]
[10, 9] -> [9]
[10] -> [10]

已经有 7 个子问题的最优解之后，可以发现一种组合方式得到原问题的最优解：f(6)f(6) 的结果 [2,5,7], 7 < 187<18，同时长度也是 f(1)f(1)~f(7)f(7) 中，结尾小于 18 的结果中最长的。f(7)f(7) 虽然长度为 4 比 f(6)f(6) 长，但结尾是不小于 18 的，无法组合成原问题的解。

以上组合方式可以写成一个式子，即状态转移方程

f(n)=maxf(i)+1 其中 i<n 且 a[i]<a[n]

这种思考如何通过 f(1)…f(n-1)f(1)…f(n−1) 求出 f(n)f(n) 的过程实际就是在思考状态转移方程怎么写。

总结：解决动态规划问题最难的地方有两点：

如何定义 f(n)f(n)
如何通过 f(1)f(1), f(2)f(2), … f(n - 1)f(n−1) 推导出 f(n)f(n)，即状态转移方程

1.2.1 递归

def find_max(nums, i):
    a = 1
    for j in range(i):
        if nums[j] < nums[i]:
            a = max(a, find_max(nums, j) + 1)
    return a

对应完整代码：

# 会超时 这是一个n**2的解法
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 这个函数是返回以i结尾的数组中最长的递增子序列
        def find_max(nums, i):
            a = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    a = max(a, find_max(nums, j) + 1)
            return a
        
        res = 0
        for i in range(len(nums)):
            res = max(res, find_max(nums, i))
        return res

1.2.2 自顶向下（记忆化）

递归的解法需要非常多的重复计算，如果有一种办法能避免这些重复计算，可以节省大量计算时间。记忆化就是基于这个思路的算法。在递归地求解子问题 f(1)f(1), f(2)f(2)… 过程中，将结果保存到一个表里，在后续求解子问题中如果遇到求过结果的子问题，直接查表去得到答案而不计算。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 这个函数是返回以i结尾的数组中最长的递增子序列
        def find_max(nums, i, dp: List[int]):
            if dp[i] != 0: # 记忆一下，减少重复计算
                return dp[i]
            a = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    a = max(a, find_max(nums, j, dp) + 1)
            dp[i] = a
            return a
        
        res = 0
        dp = [0]*len(nums)
        for i in range(len(nums)):
            res = max(res, find_max(nums, i, dp))
        return res

补充：参考动态规划解法n**2

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
    #  * 时间复杂度：O(n ^ 2)
    #  * 空间复杂度：O(n)
    #  * 动态规划，利用状态转移方程f(n) = max(f(i) + 1) (i < n && nums[i] < nums[n])
        n = len(nums)
        dp = [1]*n
        res = 1
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[j]+1, dp[i])
            res = max(dp[i], res)
        return res

最优解，贪心+二分 nlogn

## JAVA
class Solution {
      public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int len = 0;
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            // 大于直接添加这个其实类似于动态规划插入数字
            if (nums[i] > dp[len]) {
                dp[++len] = nums[i];
                // 利用二分将这个数插到合适的位置
            } else {
                int l = 0, r = len;
                while (l < r) {
                    int mid = ((r - l) >> 1) + l;
                    if (dp[mid] < nums[i]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                dp[l] = nums[i];
            }
        }
        return len + 1;
    }
}


### python3
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1]*n
        le = 0
        dp[0] = nums[0]
        for i in range(1, n):
            if nums[i] > dp[le]:
                le += 1
                dp[le] = nums[i]
            else:
                l,r = 0, le
                while l < r:
                    mid = (r+l)//2
                    if dp[mid] < nums[i]:
                        l = mid + 1
                    else:
                        r = mid
                dp[l] = nums[i]
        return le + 1

对于这种将问题规模不断减少的做法，我们把它称为自顶向下的方法。

1.2.3 自底向上（迭代）

在自顶向下的算法中，由于递归的存在，程序运行时有额外的栈的消耗。

有了状态转移方程，我们就知道如何从最小的问题规模入手，然后不断地增加问题规模，直到所要求的问题规模为止。在这个过程中，我们同样地可以记忆每个问题规模的解来避免重复的计算。这种方法就是自底向上的方法，由于避免了递归，这是一种更好的办法。

但是迭代法需要有一个明确的迭代方向，例如线性，区间，树形，状态压缩等比较主流的动态规划问题中，迭代方向都有相应的模式。参考后面的例题。但是有一些问题迭代法方向是不确定的，这时可以退而求其次用记忆化来做，参考后面的例题。

1.3 DP与其他算法的关系

这一章我们将会介绍分治和贪心算法的核心思想，并与动态规划算法进行比较。

1.3.1 分治

解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。

这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候，没有子问题重复出现，这是动态规划和分治的区别。

1.3.2 贪心

关于最优子结构
- 贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
- 动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
关于子问题最优解组合成原问题最优解的组合方式
- 贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
- 动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
结果正确性
- 贪心不能保证最后求得的结果是最佳的，复杂度低
- 动态规划本质是穷举法，可以保证结果是最佳的，复杂度高

	分治	动态规划	贪心
适用类型	通用	优化	优化
子问题	每个都不同	有很多重复	只有一个
最优子结构	没有要求	必须满足	必须满足
子问题数	全部都解	全部都要解	只解一个

二、线性动态规划

单串，带维度单串 dp[i][k]
双串，带维度双串dp[i][j][k]
矩阵
无串线性问题

2.1 简介

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。

CuteJ

半甜不要腻