算法动态规划

最长上升子序列LIS

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

$1 最长上升子序列

线性DP, 是动态规划中最常见的一个类型. 相比其它类型的DP, 它的状态设计变化非常多.

其中最经典的问题是 LIS, LCS, 它们分别代表了单串和双串的线性 DP 中最经典的状态表示和阶段划分

LIS 是单串线性 DP 的基础问题，它的状态表示是 dp[i] := [0..i] 以 i 结尾的最长上升子序列长度，i 作为阶段，没有附加状态。

LIS 的这种状态表示和阶段划分方法在单串线性 DP 问题中很常见。

问题

给定一个无序的整数数组，找到其中最长上升子序列的长度。

(1) 动态规划

1
2
3
4
5
6
7
8
9
10
11
dp[i] := [0..i] 上以 i 结尾的最长上升子序列长度

初始化
dp[i] = 1

答案
max(dp[i])

转移
dp[i] = 1 + max(dp[j])
0 <= j < i

$O(N^{2})$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> dp(n, 1);
        int result = 0;
        for(int i = 0; i <= n - 1; ++i)
        {
            for(int j = 0; j <= i - 1; ++j)
            {
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};

(2) 权值线段树或权值树状数组优化动态规划

1
2
dp[i] = 1 + max(dp[j])
0 <= j < i

这中形式的状态转移方程是一类可以用权值线段树或权值树状数组优化的DP转移方程。

Ref: 树状数组维护区间最值

代码

$O(N\log N)$

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
class Solution_3 {
public:
    // 树状数组优化
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        for(int i : nums)
            x.push_back(i);
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end()); // 把实际值离散化
        m = x.size();
        bit.assign(m + 1, 0); // 树状数组初始化
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            int dp = getmax(find(nums[i]) - 1) + 1;
            ans = max(ans, dp);
            add(find(nums[i]), dp);
        }
        return ans;
    }

private:
    int m;
    vector<int> x; // 此数组用于求 nums 中的值离散化之后的值

    int find(int v) // 从 nums 的值找到对应的离散化之后的值
    {
        return lower_bound(x.begin(), x.end(), v) - x.begin() + 1;
    }

    vector<int> bit; // 树状数组
    int lowbit(int x)
    {
        // 树状数组经典实现
        return x & (-x);
    }
    int getmax(int x)
    {
        // 树状数组经典实现
        int ma = 0;
        for(int i = x; i; i -= lowbit(i))
            ma = max(ma, bit[i]);
        return ma;
    }
    void add(int x, int v)
    {
        // 树状数组经典实现
        for(int i = x; i <= m; i += lowbit(i))
            bit[i] = max(bit[i], v);
    }
};

(3) 二分

从前向后枚举 i 的过程中动态维护一个有序的数组 vec, vec[i] := 长度为 i 的 LIS 的最小结尾

初始时，vec 为空，随着 i 的推进，vec 可能会变长，因为找到的 LIS 长度可能变长。

从前往后枚举 i，将 nums[i] 更新到 vec 中。nums[i] 可能插入到一个长为 len 的子序列后面，形成一个 len + 1 的子序列，插入时需要保证两点：

  1. 只能插入到一个比它小的数字后面
  2. 同时尽量插入一个尽量长的子序列后面

由于 vec[len] 是长度为 len 的 LIS 的最小结尾，因此如果 nums[i] <= vec[len]，则其它的长为 len 的子序列肯定也插入不了，那么就只能看 len - 1 长的能否插入。

找到一个最大的 len 使得 vec[len] < nums[i]，那么 nums[i] 会插入到长为 len 的子序列，形成长为 len + 1 的子序列。更新的位置就是 vec[len + 1]，如果 vec[len + 1] > nums[i]，则 vec[len + 1] = len，如果 len + 1 >= vec.size() 则将 nums[i] 插入 vec。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> vec; // vec[i] 是长度为 i 的 LIS 的最小结尾
         for(int i = 0; i < n; ++i)
        {
            // nums[i] 更新到 vec 中
            int p = lower_bound(vec.begin(), vec.end(), nums[i]) - vec.begin(); // lower_bound 得到的是可以插入 nums[i] 的最小的位置
            if((int)vec.size() > p)
                vec[p] = nums[i];
            else
                vec.push_back(nums[i]);
        }
        return (int)vec.size();
    }
};

$2 最长上升子序列的基础变形

最长上升子序列个数

问题

给定一个未排序的整数数组，找到最长递增子序列的个数。

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
dp_len[i] := 以 i 结尾的 LIS 长度
dp_cnt[i] := 以 i 结尾的 LIS 个数

初始化
dp_len[i] = 1
dp_cnt[i] = 0

转移
dp_len[i] = 1 + max(dp_len[k])
其中 0 <= k < i, s[k] < s[i]

dp_cnt[i] = sum(dp_cnt[j])
其中 j 是 0 <= k < i, s[k] < s[i] 这个范围内的 k 中使得 dp[k] 最大的 k,

代码

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
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        if(n == 1) return 1;
        vector<int> dp_len(n, 0), dp_cnt(n, 1);
        dp_len[0] = 1;
        for(int i = 1; i < n; ++i)
        {
            for(int k = 0; k < i; ++k)
            {
                if(nums[k] < nums[i])
                {
                    if(dp_len[k] > dp_len[i])
                    {
                        dp_len[i] = dp_len[k];
                        dp_cnt[i] = dp_cnt[k];
                    }
                    else if(dp_len[k] == dp_len[i])
                        dp_cnt[i] += dp_cnt[k];
                }
            }
            dp_len[i] += 1;
        }
        int max_len = 0;
        int max_cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            if(dp_len[i] > max_len)
            {
                max_len = dp_len[i];
                max_cnt = dp_cnt[i];
            }
            else if(dp_len[i] == max_len)
                max_cnt += dp_cnt[i];
        }
        return max_cnt;
    }
};

最长上升子串

最长上升子串最优解是滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        if(n == 1) return 1;
        int left = 0;
        int ans = 1;
        while(left < n)
        {
            int right = left + 1;
            int prev = nums[left];
            while(right < n && prev < nums[right])
            {
                prev = nums[right];
                ++right;
            }
            ans = max(ans, right - left);
            left = right;
        }
        return ans;
    }
};

$3 俄罗斯套娃信封

问题模型: 通过合适的排序转换为 LIS

二维

354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:
不允许旋转信封。

分析

通过排序转换为 LIS 问题后用 LIS 的二分算法。

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
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if(envelopes.empty()) return 0;
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), cmp);
        vector<int> vec;
        for(int i = 0; i < n; ++i)
        {
            int idx = lower_bound(vec.begin(), vec.end(), envelopes[i][1]) - vec.begin();
            if(idx < (int)vec.size())
                vec[idx] = envelopes[i][1];
            else
                vec.push_back(envelopes[i][1]);
        }
        return vec.size();
    }

private:
    static bool cmp(const vector<int>& vec1, const vector<int>& vec2)
    {
        if(vec1[0] == vec2[0])
            return vec1[1] > vec2[1];
        return vec1[0] < vec2[0];
    }
};

1626. 无矛盾的最佳球队

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

分析

通过排序转换为 LIS 问题后用 LIS 的 $O(N^{2})$ 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct Person
{
    int a, s;
    Person(int a, int s):a(a),s(s){}
};

struct Cmp
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        if(p1.a == p2.a)
            return p1.s < p2.s;
        return p1.a < p2.a;
    }
};

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();
        vector<Person> persons;
        for(int i = 0; i < n; ++i)
        {
            persons.emplace_back(ages[i], scores[i]);
        }
        sort(persons.begin(), persons.end(), Cmp());
        vector<int> dp(n, 0);
        dp[0] = persons[0].s;
        for(int i = 1; i < n; ++i)
        {
            int mx = 0;
            for(int j = 0; j < i; ++j)
            {
                if(persons[j].a == persons[i].a)
                    mx = max(mx, dp[j]);
                else if(persons[j].s < persons[i].s)
                    mx = max(mx, dp[j]);
            }
            dp[i] = mx + persons[i].s;
        }
        int ans = dp[0];
        for(int i = 1; i < n; ++i)
            ans = max(ans, dp[i]);
        return ans;
    }
};

面试题 17.08. 马戏团人塔

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

分析

通过排序转换为 LIS 问题后用 LIS 的 $O(N\log N)$ 的权值 BIT 优化的 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
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
struct Person
{
    int h, w;
    Person(int h, int w):h(h),w(w){}
};

struct Cmp
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        if(p1.h == p2.h)
            return p1.w > p2.w;
        return p1.h < p2.h;
    }
};

class Solution {
public:
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        if(height.empty()) return 0;
        int n = height.size();
        if(n == 1) return 1;
        vector<Person> persons;
        for(int i = 0; i < n; ++i)
            persons.push_back(Person(height[i], weight[i]));
        sort(persons.begin(), persons.end(), Cmp());
        vector<int> a(n);
        for(int i = 0; i < n; ++i)
            a[i] = persons[i].w;
        x = vector<int>();
        for(int i: a)
            x.push_back(i);
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());
        m = x.size();
        dp.assign(m + 1, 0);
        bit.assign(m + 1, 0);
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            int w_idx = find(a[i]);
            int len = 1;
            if(w_idx > 0)
                len += query(1, w_idx);
            ans = max(ans, len);
            update(w_idx + 1, len);
        }
        return ans;
    }

private:
    vector<int> x; // 所有能值排序后去重
    vector<int> dp; // 权值数组
    int m; // 权值数组的长度

    vector<int> bit; // 权值数组的树状数组

    void update(int idx, int val)
    {
        dp[idx - 1] = val;
        bit[idx] = val;
        for(int i = idx; i <= m; i += lowbit(i))
        {
            for(int j = 1; j < lowbit(i); j <<= 1)
            {
                bit[i] = max(bit[i], bit[i - j]);
            }
        }
    }

    int query(int l, int r)
    {
        int ans = dp[r - 1];
        while(true)
        {
            for(; r - lowbit(r) + 1 > l; r -= lowbit(r))
                ans = max(ans, bit[r]);
            if(r - lowbit(r) + 1 == l)
            {
                ans = max(ans, bit[r]);
                return ans;
            }
            ans = max(ans, dp[r - 1]);
            --r;
        }
    }

    int lowbit(int v)
    {
        return v & (-v);
    }

    int find(int v)
    {
        return lower_bound(x.begin(), x.end(), v) - x.begin();
    }
};

三维

面试题 08.13. 堆箱子

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

分析

三维俄罗斯套娃信封

通过排序转换为 LIS 问题后用 LIS 的 $O(N^{2})$ 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct Box
{
    int w, d, h;
    Box(int w, int d, int h):w(w),d(d),h(h){}
    bool operator<(const Box& box) const
    {
        return w < box.w && d < box.d && h < box.h;
    }
};

struct Cmp
{
    bool operator()(const Box& box1, const Box& box2) const
    {
        if(box1.h == box2.h)
        {
            return box1.d > box2.d && box1.w > box2.w;
        }
        return box1.h < box2.h;

    }
};

class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        vector<Box> a;
        for(const vector<int>& i: box)
        {
            a.push_back(Box(i[0], i[1], i[2]));
        }
        sort(a.begin(), a.end(), Cmp());
        int n = a.size();
        vector<int> dp(n, 0);
        dp[0] = a[0].h;
        for(int i = 1; i < n; ++i)
        {
            dp[i] = a[i].h;
            for(int j = 0; j < i; ++j)
                if(a[j] < a[i])
                    dp[i] = max(dp[i], dp[j] + a[i].h);
        }
        int ans = 0;
        for(int i: dp) ans = max(ans, i);
        return ans;
    }
};

$4 自定义LIS的小于

960. 删列造序 III

分析

1
2
vector<int> dp(m, 0); // dp[i]:= 考虑第 [0..i] 列, 且以 i 列结尾时候保留的列数
// dp[i] = max(dp[j]) + 1 其中 0 <= j < i 且 第 j 列 小于第i 列(定义什么叫小于)

代码

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
class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int m = A[0].size();
        vector<int> dp(m, 0); // dp[i]:= 考虑第 [0..i] 列, 且以 i 列结尾时候保留的列数
        // dp[i] = max(dp[j]) + 1 其中 0 <= j < i 且 第 j 列 小于第i 列(定义什么叫小于)
        dp[0] = 1;
        for(int i = 1; i < m; ++i)
        {
            for(int j = 0; j < i; ++j)
                if(less(j, i, A))
                    dp[i] = max(dp[i], dp[j]);
            ++dp[i];
        }
        int ans = 0;
        for(int i: dp)
            ans = max(ans, i);
        return m - ans;
    }

private:
    bool less(int j, int i, const vector<string>& A)
    {
        int n = A.size();
        for(int l = 0; l < n; ++l)
        {
            if(A[l][j] > A[l][i])
                return false;
        }
        return true;
    }
};

1048. 最长字符串链

算法1: 动态规划

  • DAG 上的 DP 求 DAG 的最长路径, Ref: DAG上的DP

算法2: 定义小于，转换为 LIS

  • 按照字符串长度升序排列整个数组，定义小于: (s < t: s 是 t 的前身)，用 LIS 的算法

646. 最长数对链

算法1: 动态规划 + 贪心

  • 按左端点升序排序, dp[i] = [i..n-1] 上的最长数对链长度

决策时用到区间问题中的贪心思想

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
struct Cmp
{
    bool operator()(const vector<int>& r1, const vector<int>& r2) const
    {
        return r1[0] < r2[0];
    }
};

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), Cmp());
        int n = pairs.size();
        vector<int> lefts(n);
        for(int i = 0; i < n; ++i)
            lefts[i] = pairs[i][0];
        vector<int> dp(n);
        dp[n - 1] = 1;
        for(int i = n - 2; i >= 0; --i)
        {
            if(pairs[i][1] >= pairs[i + 1][0])
            {
                dp[i] = dp[i + 1];
                auto it = upper_bound(lefts.begin() + i, lefts.end(), pairs[i][1]);
                int k = it - lefts.begin();
                if(k < n)
                    dp[i] = max(dp[i], 1 + dp[k]);
            }
            else
                dp[i] = 1 + dp[i + 1];
        }
        return dp[0];
    }
};

算法2: 定义小于，转换为 LIS

Share