求具体的最优决策序列

字数统计: 2.1k字 | 阅读时长: 9分

2023-11-15

摘要: 动态规划解决优化问题，求具体决策序列

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在动态规划解决的优化问题中，有时需要给出具体的最优方案。最直接的做法是额外使用一些与 DP 状态大小相同的数组，记录下来每个状态的最优解是从此前阶段的哪个状态转移过来的，这样在构造决策序列时，对于每个状态，都可以 $O(1)$ 地知道具体的最优决策。

如果 dp 数组上的信息可以确定状态转移，并且构造最优决策序列的时间复杂度不超过推导 DP 的时间复杂度，也可以不使用额外数组。

最终，在 DP 求出最优解后，通过一次递归，沿着额外数组记录的每一步“转移来源”回到初态，即可得到从初态到最优解的转移路径，也就是最优决策序列。

下面通过几个题看一下具体做法。三个题涉及到单串线性 DP、双串线性 DP、状态压缩 DP，都可以通过 DP 数组中的信息可以确定各个状态的具体决策。

其中第二题可以用单调队列优化，优化后推导 DP 的时候每个状态的决策只需要 $O(1)$，而构造最优决策序列时如果还是用 dp 中的信息的话，构造一个决策还是需要 $O(n)$，因此需要用额外的数组记录最优决策。

1092. 最短公共超序列

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

示例 1：
输入：str1 = “abac”, str2 = “cab”
输出：”cabac”
解释：
str1 = “abac” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 的第一个 “c”得到 “abac”。
str2 = “cab” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。
最终我们给出的答案是满足上述属性的最短字符串。

示例 2：
输入：str1 = “aaaaaaaa”, str2 = “aaaaaaaa”
输出：”aaaaaaaa”

提示：

1 2	1 <= str1.length, str2.length <= 1000 str1 和 str2 都由小写英文字母组成。

算法：双串线性DP

假设 str1 长度为 $n$，str2 长度为 $m$，比较显然的是 str1 + str2 肯定是满足同时以 str1 和 str2 作为子序列的字符串，其长度为 $n+m$。

当然有些元素可以去掉。可以去掉的字符 $c$ 一定是同时存在于 str1 和 str2 的，即 $c$ 是 str1 和 str2 的公共字符。

记构造的字符串为 $s$，要让 $s$ 越短，应该让 $s$ 中同时存在于 str1 和 str2 的字符尽可能多，当取到 str1 和 str2 的最长公共子序列时，$s$ 的长度取到最小值。

因此可以先求 str1 和 str2 的最长公共子序列，参考最长公共子序列LCS，这里直接给出动态规划算法：

dp[i][j] := 考虑 str1[0..i-1], str2[0..j-1] 时，LCS 的长度

答案
dp[n][m]

初始化
dp[i][j] = 0

转移
dp[i][j] = dp[i - 1][j - 1] + 1             (str1[i-1]==str2[i-1])
         = max(dp[i][j - 1], dp[i - 1][j])  (str1[i-1]!=str2[i-1])

然后在 str1 和 str2 上同时走一遍双串单向双指针。记 str1 的指针为 $i$，从 $n - 1$ 到 $0$ 推、str2 的指针为 $j$，从 $m - 1$ 到 $0$ 推。过程中维护 $result$。

当前在 $i, j$，如果 $str1[i] = str2[j]$ 那么 $str1[i]$ 与 $str2[j]$ 是 LCS 字符。那么将字符 $str1[i]$ 插入到 $result$ 末尾，然后 $i, j$ 均减 1。

如果 $str1[i] \neq str2[j]$，那么此时在 $result$ 末尾插入 $str1[i]$ 还是 $str2[j]$ 就要看 $dp$ 中的决策信息了。也就是 $dp[i][j + 1]$ 和 $dp[i + 1][j]$ 这两个是哪个转移到了 $dp[i + 1][j + 1]$，这个决策隐含了 $str1[i]$ 和 $st2[j]$ 谁有可能是 LCS 字符的信息。

若 $dp[i + 1][j] = dp[i + 1][j + 1]$，那么 $str2[j]$ 肯定不是 LCS 字符，因此插入 $str2[j]$。
若 $dp[i][j + 1] = dp[i + 1][j + 1]$，那么 $str1[i]$ 肯定不是 LCS 字符，因此插入 $str1[i]$。

代码 (C++)

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int n = str1.size(), m = str2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                if(str1[i - 1] == str2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }

        //构造最短公共超序列
        int i = n - 1, j = m - 1;
        string result;
        while(i >= 0 || j >= 0)
        {
            if(i >= 0 && j >= 0 && str1[i] == str2[j])
            {
                // dp[i + 1][j + 1] 是从 dp[i][j] 转移来的
                result.push_back(str1[i]);
                i--;
                j--;
            }
            else
            {
                if(j >= 0 && dp[i + 1][j] == dp[i + 1][j + 1])
                {
                    // dp[i + 1][j + 1] 从 dp[i + 1][j] 转移而来
                    // str2[i] 肯定不是 LCS 字符
                    result.push_back(str2[j--]);
                }
                else
                {
                    // dp[i + 1][j + 1] 从 dp[i][j + 1] 转移而来
                    // str1[i] 肯定不是 LCS 字符
                    result.push_back(str1[i--]);
                }
            }
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

656. 金币路径

给定一个数组 A（下标从 1 开始）包含 N 个整数：A1，A2，……，AN 和一个整数 B。你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+2，……，i+B 的任意一个可以跳到的位置上。如果你在下标为 i 的位置上，你需要支付 Ai 个金币。如果 Ai 是 -1，意味着下标为 i 的位置是不可以跳到的。

现在，你希望花费最少的金币从数组 A 的 1 位置跳到 N 位置，你需要输出花费最少的路径，依次输出所有经过的下标（从 1 到 N）。

如果有多种花费最少的方案，输出字典顺序最小的路径。

如果无法到达 N 位置，请返回一个空数组。

注释 :

路径 Pa1，Pa2，...，Pan 是字典序小于 Pb1，Pb2，...，Pbm 的，当且仅当第一个 Pai 和 Pbi 不同的 i 满足 Pai < Pbi，如果不存在这样的 i 那么满足 n < m。
A1 >= 0。 A2, ..., AN （如果存在） 的范围是 [-1, 100]。
A 数组的长度范围 [1, 1000].
B 的范围 [1, 100].

样例 1 :
输入: [1,2,4,-1,2], 2
输出: [1,3,5]

样例 2 :
输入: [1,2,4,-1,2], 1
输出: []

算法：单串线性DP

首先写出动态规划算法：

dp[i] := [i..n-1] 的最少花费

初始化
dp[n - 1] - 0

模板
dp[0]

状态转移
A[i] != -1 时:
dp[i] = A[i] + min(dp[j])
其中 i + 1 <= j <= min(n - 1, i + B) 且 dp[j] != -1

在求具体决策序列时。从动态规划的终态，也就是 $i=0$ 出发，首先如果 $A[0] \neq -1$，将 $0$ 加入决策序列，此后看动态规划中 $dp[i]$ 是从上一阶段的哪个状态转移过来的，也就对应的决策。

这需要考察 $i + 1 \leq j \leq \min(n - 1, i + B)$ 范围内的的 $dp[j]$，找到最小的满足 $dp[j] + A[i] = dp[i]$ 的 $j$，将 $j$ 加入决策序列。

然后令 $i = j$，继续上述操作，直到 $i = n - 1$。

代码 (C++)

推导 DP。以及构造最优决策序列的时间复杂度均为 $O(N^{2})$。

class Solution {
public:
    vector<int> cheapestJump(vector<int>& A, int B) {
        int n = A.size();
        if(A[n - 1] == -1) 
            return {};
        vector<int> dp(n, INT_MAX / 2);
        dp[n - 1] = 0;
        for(int i = n - 2; i >= 0; --i)
        {
            if(A[i] == -1) 
                continue;
            for(int j = i + 1; j <= min(n - 1, i + B); ++j)
            {
                if(dp[j] == INT_MAX / 2) 
                    continue;
                dp[i] = min(dp[i], dp[j] + A[i]);
            }
        }
        if(dp[0] == INT_MAX / 2) 
            return {};

        vector<int> result;
        int i = 0;
        while(i != n - 1)
        {
            result.push_back(i + 1);
            for(int j = i + 1; j <= min(n - 1, i + B); ++j)
            {
                if(dp[j] != INT_MAX / 2 && dp[j] + A[i] == dp[i])
                {
                    i = j;
                    break;
                }
            }
        }
        result.push_back(n);
        return result;
    }
};

优化：单调队列

状态转移方程如下：

$dp[i] = A[i] + \min\limits_{i + 1 <= j <= \min(n - 1, i + B)\atop dp[j] \neq -1}dp[j]$

其中 $\min dp[j]$ 可以用单调队列优化，不用每次都遍历 $dp[i+1, \min(n - 1, i + B)]$。参考文章单调队列优化DP。

这样推导 DP 的时间复杂度为 $O(N)$。但是构造最优决策序列仅用 $dp$ 中的信息的话还是 $O(N^{2})$，可以用额外数组 $from$ 记录每个 $dp[i]$ 的转移方向，$from[i] = j$ 表示 $dp[i]$ 由 $dp[j]$ 转移而来。。

代码 (C++)

class Solution {
public:
    vector<int> cheapestJump(vector<int>& A, int B) {
        int n = A.size();
        if(A[n - 1] == -1) 
            return {};
        vector<int> dp(n, INT_MAX / 2);
        vector<int> from(n, INT_MAX / 2);
        dp[n - 1] = A[n - 1];
        deque<int> deq;
        deq.push_back(n - 1);
        for(int i = n - 2; i >= 0; --i)
        {
            if(A[i] == -1 or deq.empty()) 
            {
                // 队列中只能保留 i, i + 1, ..., i + B - 1 (i 不压入)
                while(!deq.empty() && deq.front() > i + B - 1)
                    deq.pop_front();
                continue;
            }
            dp[i] = A[i] + dp[deq.front()];
            from[i] = deq.front();
            while(!deq.empty() && dp[i] <= dp[deq.back()])
                deq.pop_back();
            deq.push_back(i);
            // 队列中只能保留 i, i + 1, ..., i + B - 1
            while(!deq.empty() && deq.front() > i + B - 1)
                deq.pop_front();
        }
        if(dp[0] == INT_MAX / 2) 
            return {};

        vector<int> result;
        int i = 0;
        while(i != n - 1)
        {
            result.push_back(i + 1);
            i = from[i];
        }
        result.push_back(n);
        return result;
    }
};

1125. 最小的必要团队

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。

请你返回任一规模最小的必要团队，团队成员用人员编号表示。你可以按任意顺序返回答案，题目数据保证答案存在。

提示：

1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] 由小写英文字母组成
req_skills 中的所有字符串 互不相同
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] 由小写英文字母组成
people[i] 中的所有字符串 互不相同
people[i] 中的每个技能是 req_skills 中的技能
题目数据保证「必要团队」一定存在

示例 1：
输入：req_skills = [“java”,”nodejs”,”reactjs”], people = [[“java”],[“nodejs”],[“nodejs”,”reactjs”]]
输出：[0,2]

示例 2：
输入：req_skills = [“algorithms”,”math”,”java”,”reactjs”,”csharp”,”aws”], people = [[“algorithms”,”math”,”java”],[“algorithms”,”math”,”reactjs”],[“java”,”csharp”,”aws”],[“reactjs”,”csharp”],[“csharp”,”math”],[“aws”,”java”]]
输出：[1,2]

算法：状态压缩DP

首先将字符串表示的技能映射为一个整数的 id 值。这样每个人掌握的技能集合可以用一个整数表示，将每个人的技能集合放到数组 peo 中，

如果 peo[i] 的第 j 位为 1，表示第 i 个人具备 id 为 j 的技能。

定义 $dp[i][s]$ 表示考虑到 $peo[0..i-1]$ 这些人，其中选出的人具备的技能集合为 $s$ 时，从 $peo[i..n-1]$ 这些人中最少需要选的人数。

如果这样定义，目标为 dp[0][0]，边界为 dp[i][(1 << K) - 1] = 0。

如果无法组成满足技能需求的团队，则 $dp[i][s] = INF$。

下面考虑状态转移方程，当处在状态 $dp[i][s]$ 时，要做的决策是是否将 $peo[i]$ 加入集合：

如果加入，则团队的技能集合为 $s | peo[i]$，状态转移到 $dp[i+1][s | peo[i]]$
如果不加入，团队的技能集合仍然为 $s$，状态转移到 $dp[i+1][s]$

于是状态转移方程为：

$dp[i][s] = \min(dp[i+1][s|peo[i]] + 1, dp[i+1][s])$

构造最优决策序列时，从终态往初态推导，也就是按 $i=0\cdots n-1$ 推导。在状态 $dp[i][s]$ 时，通过比较 $dp[i][s]$ 与 $dp[i+1][s|peo[i]]$ 来判断是否选择 $peo[i]$，若相等，则选择。

代码 (C++)

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        mapping = unordered_map<string, int>();
        int id = 0;
        for(const string &s: req_skills)
            mapping[s] = id++;
        int n = people.size();
        peo = vector<int>(n);
        for(int i = 0; i < n; ++i)
        {
            for(const string &s: people[i])
            {
                if(mapping.count(s) == 0)
                    continue;
                peo[i] |= 1 << mapping[s];
            }
        }
        K = id;
        dp = vector<vector<int>>(n + 1, vector<int>((1 << K), -1));
        solve(0, 0);
        return get_path();
    }

private:
    unordered_map<string, int> mapping;
    vector<int> peo;
    int K;
    vector<vector<int>> dp;
    int INF = INT_MAX / 2;

    vector<int> get_path()
    {
        if(dp[0][0] == INF)
            return {-1};
        vector<int> path;
        int n = peo.size();
        int state = 0;
        for(int i = 0; i < n; ++i)
        {
            if(dp[i][state] == 0)
                return path;
            if(dp[i][state] == 1 + dp[i + 1][state | peo[i]])
            {
                path.push_back(i);
                state |= peo[i];
            }
        }
        return path;
    }

    int solve(int i, int state)
    {
        if(dp[i][state] != -1)
            return dp[i][state];

        if(state == (1 << K) - 1)
            return dp[i][state] = 0;
            
        // state > 0 还有技能尚未满足
        int n = peo.size();
        if(i == n)
            return dp[i][state] = INF;

        // state > 0 && i < n
        // 选 peo[i]
        int x = solve(i + 1, state | peo[i]);
        // 不选 peo[i]
        int y = solve(i + 1, state);

        return dp[i][state] = min(1 + x, y);
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法动态规划

求具体的最优决策序列

1092. 最短公共超序列

算法：双串线性DP

代码 (C++)

656. 金币路径

算法：单串线性DP

代码 (C++)

优化：单调队列

代码 (C++)

1125. 最小的必要团队

算法：状态压缩DP

代码 (C++)