跳转至

动态规划#
发布于2021-02-25
上次编辑2021-02-25

Introduction

适合应用动态规划求解的 最优化问题 应该具备两个要素：最优子结构 和 子问题重叠。

最优子结构：如果一个问题的最优解包含其子问题的最优解，就称此问题具有 最优子结构 性质。

重叠子问题：问题的递归算法会反复的求解相同的子问题，而不是一直生成新的子问题。

实现#

动态规划有两种等价的实现方法。第一种方法称为 带备忘的自顶向下法（Top-down with Memoization），第二种方法称为 自底向上法（Bottom-up Method）

  • 自顶向下：顶 指的是规模较大的问题，下 指的是规模较小的问题。
  • 自底向上：底 指的是规模较小的问题，上 指的是规模较大的问题。

带备忘的自顶向下法#

带备忘的自顶向下法通过递归实现，但是过程中会保存子问题的解（通常使用哈希表或者数组保存）。

当需要计算一个子问题的解时，

  1. 首先检查是否保存过该子问题的解
  2. 如果是，则直接返回保存的结果
  3. 否则，按照通常的方式计算这个子问题，并保存计算结果

自底向上法#

自底向上法（一般使用循环实现）一般需要恰当定义子问题的 规模 的概念，使得任何子问题的求解都只依赖于 更小的 子问题的求解。

因而我们可以将子问题按规模排序，按由小到大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已经求解完毕，结果已经保存。

两种方法得到的算法具有相同的渐近运行时间，但是在某些情况下，自顶向下的搜索可能并不需要考察所有可能的子问题，而是进行了某种贪心选择进行剪枝，或者只计算了自己需要的子问题。而由于没有频繁的函数调用的开销，自底向上的方法的时间复杂度通常具有更小的系数。

带备忘的自顶向下法就是按照分治的思想，将问题分解为规模更小的子问题，然后递归的去求解子问题并保存结果，是一种 按需计算。而自底向上的方法是不知道问题的规模，从最简单的问题规模出发，提前把比待求解问题规模更小的问题求解完，是一种 提前计算。

技巧#

状态压缩#

用 \(\texttt{dp}[i]\) 表示用 一个 资源完成 任务的子集 \(i\) 的情况，然后判断 增加一个 资源时完成该子集的情况。

1655. 分配重复整数
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool solve(vector<int> &boxes, vector<int> &items) {
        int m = boxes.size(), n = items.size(), N = 1 << n;
        vector<int> cost(N);

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) cost[i] += items[j];
            }
        }

        vector<bool> dp(N); dp[0] = true;

        for (int i = 0; i < m; ++i) {
            for (int j = N - 1; ~j; --j) {
                if (dp[j]) continue;
                for (int k = j; k; k = (k - 1) & j) {
                    if (boxes[i] >= cost[k] && dp[j ^ k]) {
                        dp[j] = true;
                        break;
                    }
                }
            }
        }

        return dp[N - 1];
    }

    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        unordered_map<int, int> count;
        for (auto x : nums) ++count[x];
        vector<int> boxes;
        for (auto [_, v] : count) boxes.emplace_back(v);

        return solve(boxes, quantity);
    }
};
1723. 完成所有工作的最短时间
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size(), N = 1 << n;
        vector<int> cost(N);

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) cost[i] += jobs[j];
            }
        }

        auto dp = cost;
        while (--k) {
            for (int i = N - 1; ~i; --i) {
                for (int j = i; j; j = (j - 1) & i) {
                    dp[i] = min(dp[i], max(cost[j], dp[i ^ j]));
                }
            }
        }

        return dp[N - 1];
    }
};

例题#

  1. 《算法导论》第 15 章 - 动态规划 ↩

返回顶部

在手机上阅读