c/c++语言开发共享完全背包&&区间dp&&最长上升子序列（南昌理工学院ACM集训队）

做了许多动态规划题目，结合yxc大大的视频，总结了一点动态规划模板，用几道经典例题加以解释

dp 第一步——状态表示（dp[i][]j）； 个人感觉一道动态规划题最难的一步就是状态表示，有一个清晰直观的状态表示做题时便势如破竹。状态标识包括集合和属性两点，集合是题目中的各个要素结合所形成的状态，属性则是题目要求状态的情况。

dp 第二步——状态计算（状态转移方程）；根据自己写的状态表示来建立状态转移方程，确立状态转移方程的同时也需考虑其复杂度。

dp 第三步——状态转移方程的优化；初学者可以先明白动态转移方程的朴素写法，然后分析题目条件进行等价变换，有一些状态转移方程的优化难以推导，可以试着打表找规律

完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000

完全背包和01背包区别在于每种物品可以无限使用，先按01背包方式建立状态转移方程，由于完全背包特性我们发现需要三重循环，复杂度约为O（n3），根据数据范围预估是肯定超时的
以下为朴素做法

#include<iostream> using namespace std;  const int N = 1010;  int n, m; int dp[N][N], v[N], w[N];//建立动态转移方程  int main(){     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 = 0; j <= m; j ++ )             for(int k = 0; 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; }  

显而易见啊，这种写法肯定会超时，这时候就需要进行优化

优化的原理就是：
dp[i][j – v] = max(dp[i – 1][j – v], dp[i – 1][j – 2 * v] + w, dp[i – 1][j – 3 * v] + 2 * w, …)；
而我们需要的dp[i][j]的状态表示是：
dp[i][j]= max(dp[i – 1][j], dp[i – 1][j – v] + w, dp[i – 1][j – 2 * v] + 2 * w, dp[i – 1][j – 3 * v] + 3 * w);
将每一项一一比对，我们可以得到下列状态表示:
dp[i][j] = max(dp[i – 1][j], dp[i][j – v] +w)；

利用优化后的状态转移方程可以轻松把复杂度降低到O（n2）

以下为优化后的写法

#include<iostream> using namespace std;  const int N = 1010;  int n, m; int dp[N][N], v[N], w[N];  int main(){     cin >> n >> m;     for(int i = 1; i <= n; i ++ ){         int v, w;         cin >> v >> w;         for(int j = 0; j <= m; j ++ ){             dp[i][j] = dp[i - 1][j];             if(j >= v)                 dp[i][j] = max(dp[i][j], dp[i][j - v] + w);         }     }     cout << dp[n][m] << endl; }  

很多人都只知道优化后的写法，但不知道是怎么来的。所以说想要优化就先得把朴素写法写出来，然后才能进一步优化。这样才能吃透大佬们的玄学做法

区间dp

区间dp入门经典那必须是石子合并啊，上题

设有N堆石子排成一排，其编号为1，2，3，…，N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24；

如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式
第一行一个数N表示石子的堆数N。

第二行N个数，表示每堆石子的质量(均不超过1000)。

输出格式
输出一个整数，表示最小代价。

数据范围
1≤N≤300

第一步建立状态表示dp[i][j]
所有第i堆石子到第j堆石子的合并方式
属性为代价最小
第二步状态计算
根据题意设一个分割点k;
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] – s[i – 1])
根据区间dp模板

for (int i = 1; i <= n; i++) {     dp[i][i] = 初始值 } for (int len = 2; len <= n; len++)           //区间长度     for (int i = 1; i + len - 1 <= n; i++) { //枚举起点         int j = i + len - 1;                 //区间终点         for (int k = i; k < j; k++) {        //枚举分割点，构造状态转移方程             dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);         }     } 

代码如下

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<string> using namespace std;  int n,rock[305],s[305]; int dp[305][305] = { 0 };  int min(int a,int b) {     if (a > b) {         return b;     }     else {         return a;     } }  int main() {     cin >> n;     for (int i = 1; i <= n; i++) {         scanf("%d", &s[i]);         s[i] += s[i - 1];     }     for (int len = 2; len <= n; len++) {//假设石子只有len个         for (int i = 1; i + len - 1 <= n; i++) {//从第i个             int j = i + len - 1;//定义为             dp[i][j] = 1e8;//为求最小值初始化             for (int k = i; k < j; k++) {//对分割点k进行枚举                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);             }         }     }     cout << dp[1][n] << endl;     return 0;                             }  

啊这。。。这题优化我不会（=￣ω￣=）

最长递增子序列

HDU1257.

这一题可以用贪心做，假设发射了很多高度无穷大的炮弹，在读入第1个炮弹时，一个导弹下降来拦截。以后每读入一个新的炮弹，都由能拦截它的最低的那个导弹来拦截，最后统计用于拦截的个数，也就是最少需要的导弹系统的套数
dp方法

首先定义状态dp[i],表示以第i个数为结尾的最长递增子序列的长度，那么：
第二部计算状态转移方程 dp[i]=max{0,dp[j]}+1
复杂度为O（n2）
代码如下

 #include <iostream> #include <string> #include <cstring> #include <cmath> #include <queue> using namespace std;  const int MAXN = 10000; int n, high[MAXN]; int LIS() { 	int ans = 1; 	int dp[MAXN]; 	dp[1] = 1; 	for (int i = 2; i <= n; i++) { 		int max = 0; 		for (int j = 1; j < i; j++) { 			if (dp[j] > max && high[j] < high[i]) 				max = dp[j]; 			dp[i] = max + 1; 			if (dp[j] > ans)ans = dp[i]; 		} 	} 	return ans;  }  int main() { 	while (cin >> n) { 		for (int i = 1; i <= n; i++) { 			cin >> high[i]; 		} 		cout << LIS() << endl; 	} 	return 0; }  

c/c++开发分享完全背包&&区间dp&&最长上升子序列（南昌理工学院ACM集训队）地址：https://blog.csdn.net/zhangjie132761/article/details/107889593