算法动态规划

环形DP

字数统计: 4k字   |   阅读时长: 18分
,

摘要: 环形结构上的动态规划

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

$0 环形结构上的 DP

对于环形结构上的 DP，比较直接的思路是：

通过枚举法，选择一个位置将环断开，变成线性结构后进行线性结构上的 DP，最后根据每次枚举的结果求出答案。

可以通过以上方法求解的环形 DP 问题称为 可拆解的环形DP问题。

在此基础上，可以采取适当的策略避免枚举，降低时间复杂度。比较常见的策略有两种。

$1 两次DP

根据环形边界的特点，将问题拆成两部分。每一部分都可以用线性结构上的 DP 求解，同时两个部分合起来可以覆盖整个问题。

288. 休息时间

在某个星球上，一天由 N 个小时构成，我们称0点到1点为第1个小时、1点到2点为第2个小时，以此类推。

在第 i 个小时睡觉能够恢复Ui点体力。

在这个星球上住着一头牛，它每天要休息B个小时。

它休息的这B个小时不一定连续，可以分成若干段，但是在每段的第一个小时，它需要从清醒逐渐入睡，不能恢复体力，从下一个小时开始才能睡着。

为了身体健康，这头牛希望遵循生物钟，每天采用相同的睡觉计划。

另外，因为时间是连续的，即每一天的第N个小时和下一天的第1个小时是相连的（N点等于0点），这头牛只需要在每N个小时内休息够B个小时就可以了。

请你帮忙给这头牛安排一个睡觉计划，使它每天恢复的体力最多。

算法

如果是没有循环的 N 个小时，U[1..N] 对应第 1 个小时到第 N 个小时恢复的体力。

线性 DP 的状态表示设计为 dp[i][k][s]，其中 i = 1,2,...,N 为考虑的小时数，作为 DP 的阶段，k 和 s 为附加状态，k 表示至少休息的小时数(0 <= k <= i)，s = {0, 1} 用于表示前一小时是否为休息状态。

当前小时 i 休息时，能否恢复 U[i] 体力取决于前一小时是否处于休息状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
dp[i][k][s] := 考虑 [1..i]，共 i 小时，恢复体力最大值
               [1..i] 这 i 小时中休息 k 小时
                s = 0: i 时处于未休息状态
                s = 1: i 时处于休息状态

初始化  
(i = 1 的情况，不论是否休息，恢复均为 0)
dp[1][0][0] = 0
dp[1][1][1] = 0

答案
max(dp[N][B][0], dp[N][B][1])

i 小时不休息 (i > k)
dp[i][k][0] = max(dp[i - 1][k][1], dp[i - 1][k][0])
i 小时休息 (k > 0)
dp[i][k][1] = max(dp[i - 1][k - 1][0], dp[i - 1][k - 1][1] + U[i])

以上线性 DP 解决的线性数组上的问题，比环形数组上的问题少考虑了一种情况：第 1 小时休息时，前一小时可能是休息的，此时 U[1] 应该加上。

用同一个动态规划算法单独求一次漏掉的这种情况，仅初始化和答案需要修改，强制第 1 小时和第 N 小时休息。

1
2
3
4
5
初始化
dp[1][1][1] = U[1]

答案
dp[N][B][1]

代码 (C++)

记忆化搜索

注：内存超限 (MLE)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <climits>
#include <vector>

using namespace std;

vector<vector<vector<int>>> dp;

void solve(const vector<int>& U, int i, int k)
{
    if(dp[i][k][1] != -1)
        return;

    if(k > 0)
    {
        // 第 i 小时休息
        solve(U, i - 1, k - 1);
        dp[i][k][1] = max(dp[i][k][1], dp[i - 1][k - 1][1] + U[i]);
        dp[i][k][1] = max(dp[i][k][1], dp[i - 1][k - 1][0]);
    }
    if(i > k)
    {
        // 第 i 小时不休息
        solve(U, i - 1, k);
        dp[i][k][0] = max(dp[i][k][0], dp[i - 1][k][0]);
        dp[i][k][0] = max(dp[i][k][0], dp[i - 1][k][1]);
    }
    if(dp[i][k][0] == -1)
        dp[i][k][0] = INT_MIN;
    if(dp[i][k][1] == -1)
        dp[i][k][1] = INT_MIN;
}

int main()
{
    int N, B;
    cin >> N >> B;
    vector<int> U(N + 1);
    for(int i = 1; i <= N; ++i)
        cin >> U[i];

    dp.assign(N + 1, vector<vector<int>>(B + 1, vector<int>(2, -1)));
    dp[1][0][0] = 0;
    dp[1][1][1] = 0;
    solve(U, N, B);
    solve(U, N, B);
    int ans1 = dp[N][B][1];
    int ans2 = dp[N][B][0];
    int ans = max(ans1, ans2);

    dp.assign(N + 1, vector<vector<int>>(B + 1, vector<int>(2, -1)));
    dp[1][0][0] = INT_MIN;
    dp[1][1][1] = U[1];
    solve(U, N, B);
    int ans3 = dp[N][B][1];
    ans = max(ans, ans3);
    cout << ans << endl;
}

滚动数组优化

i 这一维开 2，用位运算维护相邻的两个阶段。

1
2
3
4
i 小时不休息 (i > k)
dp[i & 1][k][0] = max(dp[(i - 1) & 1][k][1], dp[(i - 1) & 1][k][0])
i 小时休息 (k > 0)
dp[i & 1][k][1] = max(dp[(i - 1) & 1][k - 1][0], dp[(i - 1) & 1][k - 1][1] + U[i])

i 这一维只开 1，倒序枚举附加状态。(类似01背包)

代码 (C++)

用滚动数组不能用记忆化搜索。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <climits>
#include <vector>

using namespace std;

vector<vector<int>> dp;

void solve(const vector<int>& U, int N, int B)
{
    for(int i = 2; i <= N; ++i)
    {
        for(int k = B; k >= 0; --k)
        {
            if(i > k)
            {
                // 第 i 小时不休息
                dp[k][0] = max(dp[k][1], dp[k][0]);
            }
            if(k > 0)
            {
                // 第 i 小时休息
                dp[k][1] = dp[k - 1][0];
                if(dp[k - 1][1] >= 0)
                    dp[k][1] = max(dp[k - 1][1] + U[i], dp[k][1]);
            }
        }
    }
}

int main()
{
    int N, B;
    cin >> N >> B;
    vector<int> U(N + 1);
    for(int i = 1; i <= N; ++i)
        cin >> U[i];

    dp.assign(B + 1, vector<int>(2, -1));
    dp[0][0] = 0;
    dp[1][1] = 0;
    solve(U, N, B);
    int ans1 = dp[B][1];
    int ans2 = dp[B][0];
    int ans = max(ans1, ans2);

    dp.assign(B + 1, vector<int>(2, -1));
    dp[1][1] = U[1];
    solve(U, N, B);
    int ans3 = dp[B][1];
    ans = max(ans, ans3);
    cout << ans << endl;
}

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

提示：

1
2
1 <= nums.length <= 100
0 <= nums[i] <= 1000

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：
输入：nums = [1,2,3]
输出：3

算法：动态规划

如果是线性结构，打家劫舍的动态规划算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[i] := 考虑到 i ，nums[0..i] 选出的不相邻子数组最大和

初始化
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

答案
dp[n - 1]

状态转移：
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])

由于数组是环形数组。用线性数组的动态规划算法最后会多考虑一种情况，即 nums[0] 和 nums[n - 1] 均选了，环形的情况这两个最多只能选一个，因此至少有一个是不选的。

为了避免这种情况，可以按照不选 nums[n - 1] 和不选 nums[0] 分为两部分。

不选 nums[n - 1] 相当于在 nums[0..n-2] 上求解。

不选 nums[0] ，相当于在 nums[1..n-1] 上求解。

这样就将环形 DP 变为了两次线性 DP。

代码 (C++)

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
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) 
            return 0;
        int n = nums.size();
        if(n == 1) 
            return nums[0];
        return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
    }

private:
    int solve(vector<int>& nums, int left, int right)
    {
        int n = right - left + 1;
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[left];
        int mx0 = nums[left], mx1 = max(nums[left], nums[left + 1]);
        for(int i = left + 2; i <= right; ++i)
        {
            int mx = max(mx1, mx0 + nums[i]);
            mx0 = mx1;
            mx1 = mx;
        }
        return mx1;
    }
};

1388. 3n 块披萨

抽象成环形数组上的打家劫舍。

题解参考：力扣1388-3n块披萨

$2 复制一倍接在末尾

在任意位置将环断开成链，复制一倍接在末尾。

这种做法在二倍长度的线性数组上做 DP 时需要控制好长度，这在区间 DP 中是很好控制的，因为区间 DP 的区间长度恰好就是 DP 的阶段，再加上左端点这个附加状态小于 (int)A.size()，则可以覆盖环形数组的所有子数组同时不产生非法状态。

283. 多边形

游戏开始时，给定玩家一个具有N个顶点N条边（编号1-N）的多边形，如图1所示，其中N = 4。

每个顶点上写有一个整数，每个边上标有一个运算符 +（加号）或运算符 *（乘号）。

第一步，玩家选择一条边，将它删除。

接下来在进行N-1步，在每一步中，玩家选择一条边，把这条边以及该边连接的两个顶点用一个新的顶点代替，新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到的结果。

最终，游戏仅剩一个顶点，顶点上的数值就是玩家的得分，上图玩家得分为0。

请计算对于给定的N边形，玩家最高能获得多少分，以及第一步有哪些策略可以使玩家获得最高得分。

算法：环形数组上的区间DP

初始时，N 个数字和N 个符号是环形连接的结构。第一步需要选一个符号断开。形成一个 N 个数字，N - 1 个符号的线性数组。

在任意位置断开，用断开的符号将两个【N 个数字，N - 1 个符号的线性数组】连接在一起。之后在这个拼接后的数组上进行区间 DP。

区间DP算法如下：

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
dp[i][j] := 将 [i, j] 合成一个点的最大值
dp2[i][j] := 将 [i, j] 合成一个点的最小值

初始化
dp[i][i] := nums[i]
dp2[i][i] := nums[i]

转移
其中 ops[k] = t 表示加法，x 表示乘法
加法：
dp[i][j] = max(dp[i][k - 1] + dp[k][j]);
dp1[i][j] = min(dp[i][k - 1] + dp[k][j]);
乘法: 
dp[i][j] = max(
            max(dp[i][k - 1] * dp[k][j]);
            max(dp1[i][k - 1] * dp[k][j]);
            max(dp[i][k - 1] * dp1[k][j]);
            max(dp1[i][k - 1] * dp1[k][j]);
        )
dp1[i][j] = min(
            min(dp[i][k - 1] * dp[k][j]);
            min(dp1[i][k - 1] * dp[k][j]);
            min(dp[i][k - 1] * dp1[k][j]);
            min(dp1[i][k - 1] * dp1[k][j]);
        )

代码 (C++)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <vector>
#include <string>
#include <iostream>
#include <climits>

using namespace std;

void solve(const string& ops, const vector<int>& nums, const int max_len)
{
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, INT_MIN));
    vector<vector<int>> dp2(n, vector<int>(n, INT_MAX));
    for(int i = 0; i < n; ++i)
    {
        dp[i][i] = nums[i];
        dp2[i][i] = nums[i];
    }
    for(int len = 2; len <= max_len; ++len)
        for(int i = 0; i <= n - len; ++i)
        {
            int j = i + len - 1;
            for(int k = i + 1; k <= j; ++k)
            {
                if(ops[k] == 't')
                {
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k][j]);
                    dp2[i][j] = min(dp2[i][j], dp2[i][k - 1] + dp2[k][j]);
                }
                else
                {
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] * dp[k][j]);
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] * dp2[k][j]);
                    dp[i][j] = max(dp[i][j], dp2[i][k - 1] * dp[k][j]);
                    dp[i][j] = max(dp[i][j], dp2[i][k - 1] * dp2[k][j]);
                    dp2[i][j] = min(dp2[i][j], dp[i][k - 1] * dp[k][j]);
                    dp2[i][j] = min(dp2[i][j], dp[i][k - 1] * dp2[k][j]);
                    dp2[i][j] = min(dp2[i][j], dp2[i][k - 1] * dp[k][j]);
                    dp2[i][j] = min(dp2[i][j], dp2[i][k - 1] * dp2[k][j]);
                }
            }
        }
    int ans = dp[0][max_len - 1];
    vector<int> cands(1, 0);
    for(int i = 1; i < max_len; ++i)
    {
        if(dp[i][i + max_len - 1] > ans)
        {
            ans = dp[i][i + max_len - 1];
            cands.clear();
            cands.push_back(i);
        }
        else if(dp[i][i + max_len - 1] == ans)
            cands.push_back(i);
    }
    cout << ans << endl;
    for(int i: cands)
        cout << i + 1 << " ";
    cout << endl;
}

int main()
{
    int N;
    cin >> N;
    string ops(N, ' ');
    vector<int> nums(N);
    for(int i = 0; i < N; ++i)
    {
        cin >> ops[i];
        cin >> nums[i];
    }
    nums.insert(nums.end(), nums.begin(), nums.end());
    ops.insert(ops.end(), ops.begin(), ops.end());
    solve(ops, nums, N);
};

289. 环路运输

在一条环形公路旁均匀地分布着N座仓库，编号为1~N，编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 $dist(i,j)=\min⁡(|i-j|,N-|i-j|)$，也就是逆时针或顺时针从 i 到 j 中较近的一种。

每座仓库都存有货物，其中编号为 i 的仓库库存量为 Ai。

在 i 和 j 两座仓库之间运送货物需要的代价为 $Ai+Aj+dist(i,j)$。

求在哪两座仓库之间运送货物需要的代价最大。

算法：环形数组上的线性DP

在任意位置把环断开，然后复制一倍接在末尾。形成长 2N 的线性公路。其中 A[i] = A[i + N]。

由距离的定义 $dist(i,j)=\min⁡(|i-j|,N-|i-j|)$，可以推出：

对长为 $N$ 的环形公路的任意两点 $(i, j)$，满足 0 <= i < j <= N - 1，有：

  • 如果 j - i <= N / 2，则在 2N 长线性公路上，仍对应成 $(i, j)$ 这两个点。代价为 A[i] + A[j] + i - j。
  • 如果 j - i > N / 2，则在 2N 长线性公路上，对应成 $(j, i + N)$。代价为 A[j] + A[i + N] + i + N - j

把两种情况合到一起，问题转化为：

长为 2N 的数组 A 上，满足 0 <= i < j <= 2N - 1，且 j - i <= N / 2 时，$A[i] + A[j] + j - i$ 的最大值。

枚举 j，对每个 j，找一个 j - N / 2 <= i <= j - 1，使得 $A[i] - i$ 尽量大。

这是滑动窗口最大值问题，用单调队列可以摊销 O(1) 求出每个 j 对应的最大 A[i] - i。

注：这种在任意位置把环断开，然后复制一倍接在末尾的处理方式与环形最大字段和的前缀和+单调队列的处理方式相同。参考文章 环形数组上的最大子数组和。

代码 (C++)

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
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; ++i)
        cin >> A[i];
    A.insert(A.end(), A.begin(), A.end());
    int ans = 0;
    deque<int> deq;
    deq.push_back(0);
    for(int j = 1; j < N * 2; ++j)
    {
        // 对每个 j 找 j - N /2 <= i <= j - 1 中 A[i] - i 的最大值
        // 此时 deq 中是 [j - N / 2, j - 1]

        // 更新答案
        ans = max(ans, A[j] + j + A[deq.front()] - deq.front());

        // 插入 j 保持单调性
        while(!deq.empty() && A[deq.back()] - deq.back() <= A[j] - j)
            deq.pop_back();
        deq.push_back(j);

        // 弹出 <= j - N / 2 的保持区间合法性
        if(!deq.empty() && deq.front() <= j - N / 2)
            deq.pop_front();
    }
    cout << ans << endl;
}
Share