算法模板7：动态规划+贪心

文章目录


萨尔镇楼
在这里插入图片描述

五. 动态规划

5.1 背包问题

dp[j] 表示在容量为 j 的背包中，能够获得的最大价值。

01背包模板

每个物品只能选一次。

for (int i = 1; i <= n; i++) {        // 遍历物品
    for (int j = m; j >= w[i]; j--) { // 遍历容量，从大到小
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
完全背包模板

每个物品可以选无限次。

for (int i = 1; i <= n; i++) {       // 遍历物品
    for (int j = w[i]; j <= m; j++) { // 遍历容量，从小到大
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
多重背包模板

每个物品有固定数量。

for (int i = 1; i <= n; i++) {
    for (int k = 1; k <= s[i]; k++) { // 枚举每个物品的数量
        for (int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

5.2 线性 DP

最大子数组和

在一个整数数组中找到一个具有最大和的连续子数组。

dp[i] 表示以第 i 个元素结尾的最大子数组和。

int dp[n]; 
dp[0] = a[0];
int res = dp[0];
for (int i = 1; i < n; i++) {
    dp[i] = max(a[i], dp[i - 1] + a[i]);
    res = max(res, dp[i]);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
最长递增子序列: LIS模板

dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

/*
    状态转移dp[i] = max{ 1.dp[j] + 1 };  j
void solve(){   // 参考挑战程序设计入门经典;
    for(int i = 0; i < n; ++i){  
        dp[i] = 1;  
        for(int j = 0; j < i; ++j){  
            if(a[j] < a[i]){  
                dp[i] = max(dp[i], dp[j] + 1);  
            } } }
}  
/* 
    优化方法：
    dp[i]表示长度为i+1的上升子序列的最末尾元素  
    找到第一个比dp末尾大的来代替 
*/

    void solve() {  
        for (int i = 0; i < n; ++i){
            dp[i] = INF;
        }
        for (int i = 0; i < n; ++i) {  
            *lower_bound(dp, dp + n, a[i]) = a[i];  //  返回一个指针  
        }  
        printf("%d\n", *lower_bound(dp, dp + n, INF) - dp;  
    }
/*  
    函数lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个不小于value的值。
*/
  • 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
最长公共子序列 LCS
  • dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子序列的长度。
void solve() {  
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {  
            if (s1[i] == s2[j]) {  
                dp[i + 1][j + 1] = dp[i][j] + 1;  
            }else {  
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);  
            } } }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

5.3 区间 DP

  • 求解需要分割或合并区间的最优值。
  1. 戳气球：LeetCode 312。
  2. 石子合并问题：AcWing 282。
for (int len = 2; len <= n; len++) {      // 枚举区间长度
    for (int l = 1; l + len - 1 <= n; l++) { // 枚举左端点
        int r = l + len - 1;              // 计算右端点
        for (int k = l; k < r; k++) {     // 枚举分割点
            dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + cost);
        } }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

5.4 状态压缩 DP

  • 适用于子集问题，利用位运算压缩状态。
  • 状态表示为某个集合的子集。
  1. 旅行商问题（TSP）：AcWing 91。
  2. 划分子集和问题：LeetCode 698。
for (int mask = 0; mask < (1 << n); mask++) {  // 枚举所有状态
    for (int i = 0; i < n; i++) {             // 枚举当前状态下可选元素
        if (mask & (1 << i)) {
            dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + cost);
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

5.5 树形 DP

  • 用于树形结构的最优值问题。
  1. 树的直径：LeetCode 124。
  2. 树的最大路径和：AcWing 285。
void dfs(int u, int parent) {
    for (int v : graph[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u] = max(dp[u], dp[v] + value[v]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

5.6 记忆化搜索

  • 使用递归 + 记忆化数组避免重复计算。
  • 自底向上递归。
  1. 爬楼梯问题：LeetCode 70。
  2. 三角形最小路径和：LeetCode 120。
int dfs(int u) {
    if (vis[u]) return dp[u];
    vis[u] = 1;
    dp[u] = ...; // 状态转移
    return dp[u];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

六. 贪心

6.1 区间选点

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。

思路：

  1. 将所有区间按照右端点排序
  2. 遍历所有区间，ed 初始化为无穷小
    如果本次区间不能覆盖上次区间的右端点，ed 如果本次区间可以覆盖上次区间的右端点，则进行下一轮循环
#include
using namespace std;
int n;
struct SS{
    int l,r;
}e[100010];
bool cmp(SS x,SS y)
{
    return x.r<y.r;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        e[i]={x,y};
    }
    sort(e+1,e+1+n,cmp);
    int ed=-2e8,res=0;
    for(int i=1;i<=n;i++)
    {
        if(e[i].l>ed)
        {
            res++;
            ed=e[i].r;
        }
    }
    cout<<res;
    return 0;
}
  • 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

6.2 区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。

应用场景：
有若干个活动，第 i 个活动开始时间和结束时间是 [SiSi,fifi]，同一个教室安排的活动之间不能交叠，求要安排所有活动，少需要几个教室？

思路：

  1. 将所有区间按照左端点从小到大排序
  2. 用小根堆维护每一个不相交区间的右端点的最大值
  3. 若区间之间有交集，那么增加一个新的教室
#include
using namespace std;
int n;
struct SS{
    int l,r;
}e[100010];
bool cmp(SS x,SS y)
{
    return x.l<y.l;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        e[i]={x,y};
    }
    sort(e+1,e+1+n,cmp);
    //用小根堆来维护所有组右端点的最大值
    //堆中每一个值存的是每个组的右端点的最大值 
    priority_queue<int,vector<int>,greater<int>>heap;
    for(int i=1;i<=n;i++)
    {
        auto t=e[i];
        //若堆为空或者堆顶元素 >= 现在区间左端点，说明有交集，不能合并 
        if(heap.empty()||heap.top()>=t.l) heap.push(t.r);
        else
        {
            //更新当前区间的右端点 
            heap.pop(); 
            heap.push(t.r);
        }
    }
    //输出组数 
    cout<<heap.size();
    return 0; 
}
  • 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

6.3 区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 -1。

思路：

  1. 根据所有区间的左端点从小到大排序
  2. 从前往后枚举每个区间，在所有能覆盖 st 的区间里，选择右端点最大的区间，然后将 st 更新为右端点的最大值
#include
using namespace std;
int st,ed;
int n;
struct SS{
    int l,r;
}e[100010];
bool cmp(SS x,SS y)
{
    return x.l<y.l;
}
int main()
{
    cin>>st>>ed;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        e[i]={x,y};
    }
    sort(e+1,e+1+n,cmp);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int j=i,r=-2e8; 
        while(j<n&&e[j].l<=st)//寻找右端点最大的左端点能覆盖st的区间
        {
            r=max(r,e[j].r);
            j++;
        }
        if(r<st)//不能覆盖区间 
        {
            cout<<"-1";
            break;
        }
        res++;//寻找一次，次数+1
        st=r;//更新st 
        if(r>=ed)//已经覆盖区间 
        {
            cout<<res;
            break;
        }
        i=j-1;
    }   
    return 0;
}
  • 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

6.4 最大不相交区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。

思路：

  1. 根据所有区间的右端点从小到大排序
  2. 从前往后枚举每个区间，如果当前区间已经包含点，则 pass，否则，选择当前区间的右端点
    3.ps: 该题实质上是区间选点的本质
#include
using namespace std;
int n;
struct SS{
    int l,r;
}e[100010];
bool cmp(SS x,SS y)
{
    return x.r<y.r;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        e[i]={x,y};
    }
    sort(e+1,e+1+n,cmp);
    int ed=-2e8,res=0;
    for(int i=1;i<=n;i++)
    {
        if(e[i].l>ed)
        {
            res++;
            ed=e[i].r;
        }
    }
    cout<<res;
    return 0;
}
  • 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

6.5 摆动序列

如果相邻数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。例如 [1,7,4,9,2,5] 是一个摆动序列，差值 (6,-3,5,-7,3) 正负交替出现。
[1,4,7,2,5] 和 [1,7,8,6,4,2,3] 不是摆动序列。
给定一个整数序列，返回作为摆动序列的最长子序列的长度 。通过从原始序列中删除一些（也可以不删除）元素来获得 子序列，剩下的元素保持其原始顺序。
例： 输入：[1,7,4,9,2,5] ，输出 6 输入：[1,7,8,6,4,2,3] ，输出4

思路：

因为摆动序列要求正负交替出现，且数量匹配，所以维护两个变量 up 和 down，分别表示当前元素作为上升或下降趋势时的最长摆动子序列长度。
遍历数组 nums 的每个元素：
如果当前元素 nums[i] 大于前一个元素 nums[i-1]，则说明存在上升趋势，更新 up = down + 1。
如果 nums[i] 小于前一个元素 nums[i-1]，则存在下降趋势，更新 down = up + 1。
最终 max(up, down) 即为最长的摆动子序列长度。

#include 
using namespace std;

int maxLength(vector<int> nums) {
    if (nums.size() < 2) return nums.size();
    
    int up = 1, down = 1;  // 初始值设置为1，因为单个元素或相同元素序列也可以看作摆动序列
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i - 1]) {  // 上升趋势
            up = down + 1;
        } else if (nums[i] < nums[i - 1]) {  // 下降趋势
            down = up + 1;
        }
    }
    return max(up, down);
}

int main() {
	int n;
	cin>>n;
	vector<int>nums(n);
	for(int i=0;i<n;i++){
		cin>>nums[i];
	}
    cout << "最长摆动子序列长度: " << maxLength(nums) << endl;

    return 0;
}
  • 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
注：本文转载自blog.csdn.net的梓仁沐白的文章"https://blog.csdn.net/sjb2274540432/article/details/144088677"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！