完全背包&&区间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;
}
啊这。。。这题优化我不会（=￣ω￣=）
最长递增子序列
这一题可以用贪心做，假设发射了很多高度无穷大的炮弹，在读入第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;
}
本文地址：https://blog.csdn.net/zhangjie132761/article/details/107889593