跳转至

动态规划

动态规划（英语：Dynamic programming，简称 DP），是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

用动态规划解决问题的关键是写出状态转移方程，也就是如何使用子问题的结果推导出大问题的结果的方程。举一个最简单的例子：求一个数组\(a_i\)中最大的数。如果知道前\(n\)项的最大数是\(max_n\)，那么前\(n+1\)项的最大数就是：

\[max_{n+1} = max(max_n, a_{n+1})\]

（当然堆会更快，这里只是举一个例子）。以高中的知识范畴，有一点数列递推公式的感觉。在想出状态转移方程之后，明确边界条件即可。

例子

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

如果我们已经知道包含第n项的前n项的具有最大和为\(sum_n\)，那么\(\(sum_{n+1} = max(a_{n+1}, sum_n+a_{n+1})\)\)，题目的解就是\(MAX_n^N(sum_n)\)。

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

乍一看和上面一模一样。不过乘法要考虑负数。所以如果我们已经知道包含第n项的前n项的具有最大乘积为\(maxp_n\)，最小乘积为\(minp_n\)，那么状态转移方程为：\(\(maxp_{n+1} = max(a_{n+1}, maxp_n\times a_{n+1}, minp_n\times a_{n+1})\)\)，\(\(minp_{n+1} = min(a_{n+1}, maxp_n\times a_{n+1}, minp_n\times a_{n+1})\)\)，题目的解就是\(MAX_n^N(maxp_n)\)。

LeetCode 279：给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。例如，n=13，最少是2个完全平方数9+4的和。

设和为 \(x\) 的完全平方数的最少数量为\(f(x)\)，我们有\(f(x) = MIN_{a=1}^x{ f(n-a)+f(a)}\)。并且如果\(x\)是完全平方数有\(f(x) = 1\)。

还有更好的状态转移方程。考虑到我们必须要选完全平方数，\(\(f(x) = MIN_{a=1}^{\lfloor \sqrt n \rfloor} f(a^2)+f(n-a^2)\)\)

LeetCode 435：给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

求移除的最小数量等价于求互不重叠的最多数量。说来惭愧，我一开始的想法只有暴力搜索（\(O(2^n)\)的复杂度。。。），加了剪枝策略之后依然超时。将区间按照顺序排列之后，我们记\(f(x)\)为选择第x个区间时，0-x区间数量的最大值。我们有：

\[f(x) = MAX_{i<x \And r_j < l_i}(f(i)) + 1\]

互不重叠的最多数量就是\(max(f(x))\)。435. 无重叠区间 - 力扣（LeetCode）贪心算法更快。。。

LeetCode 32: 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号的长度。

背包问题

华为机考-购物单_牛客题霸_牛客网

看到这种题，我一般都直接开摆暴力搜索。。。

解法一（超时）：暴力搜索，并且这种搜索方式有很多无效路径。例如例子中购买1,2,5, 代码会反复搜索1,2,5；5,1,2；等等，时间复杂度是\(M!\)

from dataclasses import dataclass

@dataclass
class T:
    value: int
    weight: int
    depend: int

def search(sat, value):
    global max_sat
    if sat > max_sat:
        max_sat = sat
    for i in range(0,m):
        if i not in bought and (things[i].depend == 0 or things[i].depend -1 in bought) and value >= things[i].value:
            bought.add(i)
            search(sat+ things[i].value * things[i].weight, value - things[i].value)
            bought.remove(i)

if __name__ == "__main__":
    bought= set() 
    max_sat = 0
    n,m = [int(i) for i in input().split()]
    things = []
    for i in range(0,m):
        v,w,q = [int(i) for i in input().split()]
        things.append(T(v,w,q))
    search(0, n)
    print(max_sat)

优化一下，将东西按照依赖关系拓扑排序，就可以顺序搜索了。对于这道题，可以先搜主件，再搜副件。这样的时间复杂度是\(O(2^M)\)。

from dataclasses import dataclass


@dataclass
class T:
    value: int
    weight: int
    depend: int
    index: int


bought = set()
max_sat = 0


def search(index, sat, value):
    global max_sat
    if sat > max_sat:
        max_sat = sat
    for i in range(index, m):
        if (things[i].depend == 0 or things[i].depend in bought) and value >= things[i].value:
            bought.add(things[i].index)
            search(i+1, sat + things[i].value *
                   things[i].weight, value - things[i].value)
            bought.remove(things[i].index)


n, m = [int(i) for i in input().split()]
things = []
sorted_things = []
for i in range(0, m):
    v, w, q = [int(i) for i in input().split()]
    things.append(T(v, w, q, i+1))

for i in range(0, m):
    if things[i].depend == 0:
        sorted_things.append(things[i])
for i in range(0, m):
    if things[i].depend != 0:
        sorted_things.append(things[i])
things = sorted_things
search(0, 0, n)
print(max_sat)

这道题是一个典型的01背包问题，不过多了背包依赖。用动态规划解决背包问题的思路是：

如果一共有\(N\)个物品，每个价值\(v[i]\)，消耗权重\(w[i]\)，你共有\(W\)权重。求能获得的最大价值。

如果\(f[n][w]\) 是只有\(n\)个物品时，使用\(w\)权重可以获得的最大价值。那么我们有状态转移方程：

\[ f[n][w] = max(f[n-1][w], f[n-1][w-w[n]]+v[n]) \]

时间复杂度是\(O(NW)\)，空间复杂度也是\(O(NW)\)，但是可以发现实际上\(f[n]\)只依赖\(f[n-1]\)，所以实际上可以将空间复杂度优化到\(O(W)\)，这要求在编程的时候从W向0遍历w。 - 如果希望得到此时背包装了哪些物品？ - 如果只是需要输出一种组合，可以在f[n-1][w-w[n]]+v[n] > f[n-1][w] 的时候，将p[n][w] = true;最后从W倒推。 

    for (int i = N-1, j = W; i >= 0; --i)
        if (p[i][j])    // 背包有該物品
        {
            cout << "背包裡面有第" << i << "個物品";
            j -= w[i];
        }
- 如果希望得到价值大于X的最小重量？ - 可以再从小到大遍历一遍\(f[n][w]\)直到满足条件，w就是最小重量。

背包问题是NPC问题，\(O(NW)\)并不是多项式时间。只是说大部分情况下W不会很大，算法的表现还不错。

如果每个物品的数量是无限的，状态转移方程稍作修改：

\[ f[n][w] = max(f[n-1][w], f[n][w-w[n]]+v[n]) \]

这里修改了\(f[n-1][w-w[n]]\)为\(f[n][w-w[n]]\)，表示则表示在选择了第 n个物品后，后续还可以再选择它。在具体的编程时，可以直接从前往后枚举重量。

如果每个物品的数量是有上限的（每个物品最多\(m[i]\)个），可以将物品的数量分解成1, 2, 4 ..., \(2^k\), \(m[i] -2^{k+1}+1\)。这些组合可以凑出所有的情况，然后当作0-1背包处理。

void knapsack(int N, int W)
{
    for (int i = 0; i < N; ++i)
    {
        int num = min(m[i], W / w[i]);
        for (int k = 1; num > 0; k *= 2)
        {
            if (k > num) k = num;
            num -= k;
            for (int j = w; j >= w[i] * k; --j)
                c[j] = max(c[j], c[j - w[i] * k] + v[i] * k);
        }
    }
    cout << "最高的價值為" << c[w];
}

称砝码_牛客题霸_牛客网 是背包问题的变体，被称为凑钱问题money changing problem。思路上和背包问题相似。

if __name__ == "__main__":
    n = int(input())
    ms = [int(m) for m in input().split()]
    xs = [int(x) for x in input().split()]

    count = 1
    ok = [True] + [False] * 200000
    msum = 0 # msum是一个优化，可以少循环几次
    for i in range(n):
        for j in range(msum,-1,-1):
            for k in range(1, xs[i]+1):
                if ok[j]:
                    if ok[j+k*ms[i]] == False:
                        count += 1
                    ok[j+k*ms[i]] = True
        msum += ms[i]*xs[i]
    print(count)

最长公共子串、子序列

求两个字符串（记作s, t）的最长公共子串/子序列是一个经典的动态规划问题。

最长公共子串（Longest Common Substring） 与 最长公共子序列（Longest Common Subsequence） 的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。

子序列：令d[i][j]表示s[0:i]和t[0:j]的最长公共子序列的长度。我们希望知道它能否由子问题推导。

首先，如果说s[i-1]=t[i-1]，那么最长公共子序列的长度就是之前的长度+1。

\[d[i][j] = d[i-1][j-1] + 1, \text{if s[i-1]=t[i-1]}\]

如果不等，那么最长公共子序列的长度就是之前的长度的较大值。

\[d[i][j] = max(dp[i−1][j],dp[i][j−1]), \text{if s[i-1]} \neq \text{t[i-1]}\]

边界条件，是\(d[i][0] = 0, d[0][j] = 0\)。

子串：令d[i][j]表示s[0:i)和t[0:j)的包含最后一个字母的最长公共子串的长度。

递推公式有点类似，但是不同：

\[d[i][j] = d[i-1][j-1] + 1, \text{if s[i-1]=t[i-1]}$$$$d[i][j] = 0, \text{if s[i-1]=t[i-1]}\]

边界条件，同样是\(d[i][0] = 0, d[0][j] = 0\)。 他们的时间复杂度都是\(O(|s|\times|t|)\)。

最长上升子序列问题

最长上升子序列（Longest Increasing Sub-sequence）问题，指的是在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

如果是寻找一个连续的最长上升子序列，可以使用滑动窗口。

以这道题为例：300. 最长递增子序列 - 力扣（LeetCode）。

可以使用动态规划解决这个问题。如果原序列中的包含第\(i\)个元素的LIS长度为\(lislen_i\)，那么对于前\(i+1\)个元素，$$lislen[i+1] =

max({lislen[k]+1 \big| a[i+1]>a[k]}\cup{1})

$$ 这种算法的时间复杂度为\(O(n^2)\)，空间复杂度为\(O(n)\)，代码如下：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(1,n):
            for j in range(0,i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

不过这并不是最优的算法。让我们重新审视动态规划的代码，发现对于第i个元素，我们都要重新遍历之前的所有元素来找到满足\(nums[i]>nums[j]\)的\(dp[j]\)的最大值。我们可以用空间换时间来优化这个步骤。

具体的说，我们可以记录下前i-1个元素中，长度为k的上升子序列末尾的元素值最小值。以这个序列[0,1,0,3,2,4]为例，当我们遍历到3时，前三个元素中

  • 长度为1的上升子序列，末尾元素最小值为0。
  • 长度为2的上升子序列，末尾元素最小值为1。
  • 长度为3-n的上升子序列，末尾元素最小值为+inf。

事实上，末尾元素最小值是一个单调序列。这一点可以用反证法证明，这里不再赘述。

那么当我们遍历到3的时候，就可以更新

  • 使用二分查找，找到末尾元素值小于3的子序列，也就是长度为2。
  • 更新长度为3的上升子序列，末尾元素最小值为3。
class Solution:
    # 寻找最后一个比target小的值
    def binarySearch(self, lenmin: List[int], target: int):
        left, right = 0, len(lenmin)-1
        index = 0
        while right >= left:
            mid = (left + right) // 2
            if target > lenmin[mid]:
                index = mid
                left = mid + 1
            else:
                right = mid - 1
        return index

    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        ret = 1
        lenmin = [-10001]+[10001] * n
        for i in range(0, n):
            pos = self.binarySearch(lenmin, nums[i])
            lenmin[pos+1] = nums[i]
            ret = max(ret, pos+1)
        return ret

参考链接