背包问题模板

01背包问题

https://www.acwing.com/problem/content/2/

问题叙述：有N件物品和一个容量是V的背包，每个物品只能使用一次。第i件物品体积为v,价值为w,求将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值

思路：DP数组中DP[j]表示背包承重为j时的最大价值。两重循环递推，第一重循环遍历每个物品，第二重循环逆序遍历承重。对于每一个承重，都有选和不选第i的问题的抉择。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N];
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    
    cout<<dp[m]<<endl;
  return 0;
}

完全背包问题

https://www.acwing.com/problem/content/3/

题目叙述：有N种物品和容量是V的背包，每种物品无限件使用。第i种物品体积为v,价值是w,求解将哪些物品装入背包，可使得物品的总体积不超过背包容量，且总价值最大。

思路：DP数组中DP[j]表示背包承重为j时的最大价值。两重循环递推，第一重循环遍历每个物品，第二重循环正序遍历承重。对于每一个承重，都有选和不选第i的问题的抉择。

代码：

#include<bits/stdc++.h>C
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N];
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
  return 0;
}

多重背包问题1

https://www.acwing.com/problem/content/4/

题目叙述：有N个物品和容量为V的背包。第i种物品最多有s件，每件体积是v，w。求解将哪些物品装入背包，可使得物品体积总和不超过背包容量，且价值总和最大。

思路：dp数组表示前i个物品中选择，承重j时的最大价值。三重循环递推，第一重循环遍历每个物品；第二重循环遍历背包所有承重；第三重循环遍历第i个物品的选择次数，并且选择次数不能超过背包承重；对于任何一个物品都有选k个和不选k个的选择问题。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int v[N],w[N],s[N];
int dp[N][N];
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=s[i] && k*v[i]<=j;k++){
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout<<dp[n][m]<<endl;
  return 0;
}

多重背包问题2

https://www.acwing.com/problem/content/description/5/

题目叙述：与上题相同，只不过本题数据范围要比上题要大。

思路：多重背包的二进制优化问题。将一个数量为s的物品，通过二进制拆分，转化为若干个只能选一次的物品，从而将多重背包问题转化为01背包问题。对于任何一个整数s都能拆分为若干个2的幂次之和。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=20200;
int n,m;
int v[N],w[N];
int dp[N];
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s){
            cnt++;
            v[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
        }
        if(s>0){
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }
    n=cnt;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
 
  return 0;
}

分组背包问题

https://www.acwing.com/problem/content/9/

问题叙述：有N组物品和容量为V的背包，每组物品有若干个，同一组内的物品最多只能选一个。

每件物品的体积时vij,价值是wij。求解将哪些物品装入背包，可使得物品总体积不超过背包容量，且总价值最大。

思路：dp数组dp[j]表示背包容量为j时，能容纳的最大价值。三重循环递推，第一重遍历每个物品，第二重逆序遍历背包容量，第三重遍历第i组内每个物品k。若当前物品体积不超过背包容量，则更新dp[j]。每个物品k都有选和不选两种方案。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int v[N][N],w[N][N];
int s[N];
int dp[N];
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            for(int k=1;k<=s[i];k++){
                if(v[i][k]<=j){
                    dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
                }
            }
        }
    }
    
    cout<<dp[m]<<endl;
  return 0;
}

常见DP模板

数字三角形问题

https://www.acwing.com/problem/content/900/

问题叙述：数字三角形，从顶部出发向下走，每步可选择向左下方或右下方移动，一直走到最底层，找出一条路径，使得路径上数字的和最大。

思路：线性DP问题，自定向下递推，每一步两种抉择，注意最后dp[n][i]再取一遍最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=520;
const int MIN=-1e9;
int graph[N][N];
int dp[N][N];
int n;
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>graph[i][j];
        }
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=i+1;j++){
            dp[i][j]=MIN;
        }
    }
     dp[1][1]=graph[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+graph[i][j];
        }
    }
    int res=MIN;
    for(int i=1;i<=n;i++) res=max(res,dp[n][i]);
    
    cout<<res<<endl;
  return 0;
}

最长上升子序列1

https://www.acwing.com/problem/content/897/

问题叙述：给定一个长度为N的数列，求数值严格单调递增的子序列的长度最大值。

思路：dp数组dp[i]表示第i个元素为结尾的最长上升子序列的长度。第一重循环遍历每个元素，对于每个dp[i]的递推，首先将其初始化为1，之后第二重循环遍历i之前的每个元素，如果之前的元素小于当前元素，则可形成更长的子序列，更新dp[i]为当前的最大值或dp[j]+1。最终在dp数组中更新出最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1020;
int n;
int arr[N];
int dp[N];
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(arr[j]<arr[i]) dp[i]=max(dp[i],dp[j]+1);
        }
    }
    int res=-1;
    for(int i=1;i<=n;i++) res=max(res,dp[i]);
    cout<<res<<endl;
  return 0;
}

最长上升子序列2

https://www.acwing.com/problem/content/description/898/

题目叙述：题意与上题相同，但数据范围比上题要大的多。

思路：使用数组q维护长度为i的最长上升子序列的末尾元素的最小值，子序列的末尾应尽可能地小，以便给后面地元素留出更大地上升空间。基于二分查找，在数组q中找到最后一个小于arr[i]的元素，设这个元素的索引为r,则arr[i]可以接在长度为r的子序列后面，构成一个长度为r+1的子序列。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010; // 数组最大长度
int arr[N];         // 存储原始序列
// q[i]表示长度为i的递增子序列的最小结尾元素
// 注意：这里q数组的索引从1开始使用，q[0]未使用或可视为无穷小
int q[N];
int n;              // 数组实际长度
int main()
{
    // 关闭输入输出流同步，加速cin/cout
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>arr[i];
    int len = 0; // len表示当前找到的最长上升子序列的长度
    // 遍历原始数组中的每个元素
    for(int i=1; i<=n; i++){
        int l = 0, r = len; // 二分查找的范围是 [0, len]
        // 二分查找：寻找最后一个小于 arr[i] 的元素的位置
        // 循环条件 r > l，确保循环会终止
        while(r > l){
            // 计算中间点，+1 是为了避免陷入死循环
            int mid = l + r + 1 >> 1; 
            
            // q[mid] < arr[i] 意味着 arr[i] 可以接在长度为mid的子序列后面
            // 我们尝试寻找一个更长的子序列，所以移动左边界
            if(q[mid] < arr[i]) l = mid;
            // 否则，说明 mid 太大了，移动右边界
            else r = mid - 1;
        }
        
        // 循环结束后，r == l，它指向了最后一个小于 arr[i] 的元素的位置
        // 那么，arr[i]可以构成一个长度为 r+1 的新子序列
        
        // 更新最长长度
        len = max(len, r + 1);
        
        // 将 arr[i] 放置到 q 数组的 r+1 位置
        // 这表示对于长度为 r+1 的子序列，arr[i]是目前已知的最小结尾元素
        q[r+1] = arr[i];
    }
    // 输出最长上升子序列的长度
    cout << len << endl;
    return 0;
}

最长公共子序列

https://www.acwing.com/problem/content/899/

题目叙述：给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

思路：dp[i][j]表示A以i结尾，B以j结尾的LCS长度。两重循环遍历A和B的每个元素，如果A的第i个元素等于B的第j个元素，则LCS长度等于其dp[i-1][j-1]+1,当前两个元素不相等，则LCS取max(dp[i-1][j], dp[i][j-1])

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1020;
int n,m;
char arr[N],brr[N];
int dp[N][N];
int main()
{
  scanf("%d%d",&n,&m);
    scanf("%s%s",arr+1,brr+1);
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(arr[i]==brr[j]){
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
            } else {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    
    cout<<dp[n][m]<<endl;
  return 0;
}

最短编辑距离

https://www.acwing.com/problem/content/904/

题目叙述：给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：

删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

思路：dp[i][j]表示将arr[1..i]转换为brr[1..j]所需的最少操作次数，初始化dp数组，全删除或全插入两种初始化思路。两重循环递推，首先考虑插入或删除操作，之后考虑替换操作，替换操作考虑两个字符相等和不等的情况。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010; // 字符串长度的上限
int n,m;          // n: 字符串A的长度, m: 字符串B的长度
char arr[N],brr[N]; // arr存储字符串A, brr存储字符串B (1-based索引)
// dp[i][j]表示将arr[1..i]转换为brr[1..j]所需的最少操作次数
int dp[N][N];
int main()
{
    // 读取输入
    scanf("%d%s",&n,arr+1); // 读取A的长度和A字符串
    scanf("%d%s",&m,brr+1); // 读取B的长度和B字符串
    // 初始化DP表
    // 将A的前i个字符转换为空字符串，需要i次删除
    for(int i=1; i<=n; i++) dp[i][0] = i;
    // 将空字符串转换为B的前j个字符，需要j次插入
    for(int j=1; j<=m; j++) dp[0][j] = j;
    // 填充DP表
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            // 首先，考虑删除和插入操作，取它们的最小值
            // dp[i-1][j]+1 是删除arr[i]的操作
            // dp[i][j-1]+1 是插入brr[j]的操作
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);
            // 然后，考虑替换操作
            if(arr[i] == brr[j]){
                // 如果当前字符相等，不需要替换，操作次数就是dp[i-1][j-1]
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
            } else {
                // 如果当前字符不相等，需要一次替换操作，操作次数是dp[i-1][j-1] + 1
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
            }
        }
    }
    // 输出最终结果
    cout << dp[n][m] << endl;
    return 0;
}

编辑距离问题

https://www.acwing.com/problem/content/901/

题目叙述：给定n个字符串和m次询问，每次询问给出一个字符串和一个操作次数上限。对于每次询问，请求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

思路：与上一题相同，对目标字符串和询问字符串执行编辑距离操作。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char str[N][15];
int dp[15][15];
int fun(char arr[],char brr[]){
  int la=strlen(arr+1),lb=strlen(brr+1);
  
  for(int i=1;i<=la;i++) dp[i][0]=i;
  for(int j=1;j<=lb;j++) dp[0][j]=j;
  for(int i=1;i<=la;i++){
    for(int j=1;j<=lb;j++){
      dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
      if(arr[i]==brr[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
      else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
    }
  }
  return dp[la][lb];
}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    scanf("%s",str[i]+1);
  }
  
  for(int i=1;i<=m;i++){
    int res=0;
    char s[15];
    int q;
    scanf("%s%d",s+1,&q);
    for(int j=1;j<=n;j++){
      if(fun(s,str[j])<=q){
        res++;
      }
    }
    cout<<res<<endl;
  }
  return 0;
}

合并石子

https://www.acwing.com/problem/content/284/

题目叙述：有N堆石子，编号为1到N，每堆石子有一定的质量，现要将N堆石子合并为一堆。每次只能合并相邻的两堆，合并代价为两堆石子的质量之和，合并后与这两堆石子相邻的石子相邻的石子将和新堆合并，请找出一种合理的方法使得总的代价最小。

思路：区间DP问题。dp[i][j]表示合并第i堆到第j堆石子的最小代价。要将区间[i,j]合并成一堆，最后一步一定是合并两个相邻的区间[i, k] 和 [k+1, j]。为了快速求区间和，对石子重量石子做前缀和。三重循环递推，第一重循环从小到大枚举区间长度，第二重循环枚举区间左端点，第三重循环遍历从左端点到右端点的每一个点，[l,r]区间合并的代价为l到r的区间和加上dp[l][k] + dp[k+1][r]。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=320;
int n;
int arr[N]; //直接将原始数组转前缀和
int dp[N][N]; //i到j的最小花费
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>arr[i];
  for(int i=1;i<=n;i++) arr[i]+=arr[i-1];
  for(int i=2;i<=n;i++){ //枚举长度
    for(int j=1;j+i-1<=n;j++){ //枚举左端点
      int l=j,r=j+i-1;
      dp[l][r]=0x3f3f3f3f;
      for(int k=l;k<r;k++){
        dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+arr[r]-arr[l-1]);
      }
    }
  }
  cout<<dp[1][n]<<endl;
  return 0;
}

整数划分

https://www.acwing.com/problem/content/902/

题目叙述：一个正整数可以表示为若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。现给定正整数n，求n共有多少种不同的划分方法。

思路：计数DP问题。dp[i][j]表示将整数i拆分为j个数的方案数。拆分方案中有两种情况:

划分中包含 1：去掉一个 1 后，剩下 i-1 需要划分成 j-1 个数，方案数为 dp[i-1][j-1]
划分中不包含 1：所有数都 ≥2，可以将每个数减 1，相当于将 i-j 划分成 j 个数，方案数为 dp[i-j][j]

双重循环递推，第一重循环枚举总和，第二重循环枚举份数。最终累加dp[n][i]。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int mod=1e9+7;//阶乘量级防止溢出
int n;
int dp[N][N]; //总和为i,总个数为j的方案数 拆分为方案中最小值是1的和不是1两种情况
int main()
{
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  dp[1][1]=1;
  for(int i=2;i<=n;i++){//和
    for(int j=1;j<=i;j++){
      dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%mod;
    }
  }
  int res=0;
  for(int i=1;i<=n;i++) res=(res+dp[n][i])%mod;
  cout<<res<<endl;
  return 0;
}

没有上司的舞会

https://www.acwing.com/problem/content/287/

题目叙述：有N名职员，编号1到N，其关系为一颗树，父节点就是子节点的直接上司。每个职员有一个快乐指数Hi，先要召开舞会，没有职员愿意与其上司一起参会。再满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员快乐指数总和最大，求这个最大值。

思路：树形DP问题。问题转化为在树上选择一些节点，使得没有父子节点同时被选中且被选中的节点权值和最大。对于树上的每个节点 u，定义两种状态：

dp[u][0]：不选择节点 u 时，以 u 为根的子树能获得的最大快乐指数
dp[u][1]：选择节点 u 时，以 u 为根的子树能获得的最大快乐指数

使用数组模拟邻接表存树。从树的根节点向下深度优先遍历。选择当前节点x时，dp[x][1]初始值为x的快乐指数，遍历x的所有子节点递归搜索，如果选择x,则不能选择其子节点，如果不选择x,则子节点可选也可不选。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=6020;           // 最大职员数+余量
int n;                      // 职员总数
int h[N], e[N], ne[N], idx; // 邻接表存储树
int happy[N];               // 每个职员的快乐指数
int dp[N][2];               // dp[u][0/1]表示不选/选u时的最大快乐指数
bool flag[N];               // 标记节点是否有父节点
// 添加边a->b
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
// 深度优先搜索计算dp值
void dfs(int x){
    dp[x][1] = happy[x];    // 选择x时，初始值为x的快乐指数
    
    // 遍历x的所有子节点
    for(int i = h[x]; i != -1; i = ne[i]){
        int j = e[i];       // 子节点
        dfs(j);             // 递归计算子节点
        
        // 状态转移
        dp[x][1] += dp[j][0];  // 选择x，则不能选择子节点j
        dp[x][0] += max(dp[j][0], dp[j][1]); // 不选择x，子节点可选可不选
    }
}
int main()
{
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n;
    for(int i=1; i<=n; i++) cin>>happy[i];
    
    // 初始化邻接表
    memset(h, -1, sizeof(h));
    
    // 构建树
    for(int i=1; i<n; i++){
        int a, b;
        cin>>a>>b;  // b是a的直接上司
        add(b, a);  // 添加边b->a
        flag[a] = true; // 标记a有父节点
    }
    
    // 找到根节点（没有父节点的节点）
    int root = 1;
    while(flag[root]) root++;
    
    // 从根节点开始DFS
    dfs(root);
    
    // 输出结果
    cout<<max(dp[root][0], dp[root][1])<<endl;
    
    return 0;
}

滑雪

https://www.acwing.com/problem/content/903/

题目叙述：R行C列的矩阵，表示一个矩形网格滑雪场，第i行第j列的点表示滑雪场第i行第j列区域的高度，一个人从滑雪场中某个区域出发，每次可以向上下左右四个方向滑动一个单位的距离，注意从高向低滑动。求能在滑雪场中完成的最长滑雪轨迹。

思路：可用记忆化搜索优化暴力。dp[i][j]表示从某位置出发能滑行的最远距离。从任意一点x,y出发，深度优先暴力搜索，每次向比自己低的地方下滑，同时使用dp数字缓存记忆化搜过的某位置最远距离。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int r,c;
int arr[N][N];
int dp[N][N];//从某位置出发能滑行的最远距离
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int getDP(int x,int y){
  if(dp[x][y]!=-1) return dp[x][y];
  dp[x][y]=1;
  for(int i=0;i<4;i++){
    int a=x+dx[i],b=y+dy[i];
    if(a>=1 && a<=r && b>=1 &&b<=c &&arr[x][y]>arr[a][b]){
      dp[x][y]=max(dp[x][y],getDP(a,b)+1);
    }
  }
  return dp[x][y];
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>r>>c;
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      cin>>arr[i][j];
    }
  }
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      dp[i][j]=-1;
    }
  }
  int res=0;
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      res=max(res,getDP(i,j));
    }
  }
  cout<<res<<endl;
  return 0;
}

算法学习笔记-动态规划常用模板

背包问题模板

01背包问题

完全背包问题

多重背包问题1

多重背包问题2

分组背包问题

常见DP模板

数字三角形问题

最长上升子序列1

最长上升子序列2

最长公共子序列

最短编辑距离

编辑距离问题

合并石子

整数划分

没有上司的舞会

滑雪

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

算法学习笔记-动态规划常用模板

背包问题模板

01背包问题

完全背包问题

多重背包问题1

多重背包问题2

分组背包问题

常见DP模板

数字三角形问题

最长上升子序列1

最长上升子序列2

最长公共子序列

最短编辑距离

编辑距离问题

合并石子

整数划分

没有上司的舞会

滑雪

热门文章

最新文章

相关电子书