动态规划基础

等有空的时候再加讲解吧。如果仅仅是代码就能帮助到您那就太好了。

• 线性动态规划
• • 最长（不）上升/下降子序列
  • 最长公共子序列
• 数学相关
• • 划分数
  • 多重集组合数
• 背包
• • 01背包
  • 完全背包
• 区间DP
• 状压DP
• 树形DP

这里就不介绍一般的方法了，一般的方法二重循环时间复杂度 O ( n 2 ) O(n^2) O(n2)确实是有点拉了。所以我们就介绍一种利用二分的方法，可以将时间复杂度降到 O ( n l o g n ) O(nlogn) O(nlogn)的方法。

就以最长上升子序列为例。比如我给出一个数列：

4   2   3   1   5 4 2 3 1 5 4 2 3 1 5

那么我们定义 d p [ i ] dp[i] dp[i]为：长度为 i i i的最长上升子序列的末尾元素的最小值。有点绕，我们直接来看是怎么实现的吧。

首先初始化 d p dp dp数组都为最大值，也就是：

第一个元素是 4 4 4，那么就来找dp数组中第一个大于等于 4 4 4的数，然后把它替换为 4 4 4。这里很明显，第一个大于四的就是 d p [ 1 ] dp[1] dp[1]，那么就把 d p [ 1 ] dp[1] dp[1]变为 4 4 4。

第二个元素是 2 2 2，第一个大于等于 2 2 2的是 d p [ 1 ] = 4 dp[1]=4 dp[1]=4，那么就再进行替换：

第三个元素是 3 3 3，第一个大于等于 3 3 3的是 d p [ 2 ] = ∞ dp[2]=∞ dp[2]=∞，那么就再进行替换：

第四个元素是 1 1 1，第一个大于等于 1 1 1的是 d p [ 1 ] = 2 dp[1]=2 dp[1]=2，那么就再进行替换：

最后一个元素是 5 5 5，第一个大于等于 5 5 5的是 d p [ 3 ] = ∞ dp[3]=∞ dp[3]=∞，再进行替换：

所有的元素都处理掉了，最后只要 f o r for for一遍看看直到几它都小于 ∞ ∞ ∞，很明显这里是 3 3 3。所以最长上升子序列长为 3 3 3。

这里的代码实现使用了 S T L STL STL库里的 l o w e r _ b o u n d lower_bound lower_bound函数。这个函数的意思就是：

int pos = (int)(lower_bound(dp + 1, dp + 1 + n, a[i]) - dp);

在 d p dp dp函数里面找到第一个大于等于 a [ i ] a[i] a[i]的值，并返回其地址。 u p p e r _ b o u n d upper_bound upper_bound则是第一个大于的。

代码实现如下：

#include  
#include  
#include  
#include  
using namespace std;
int dp[100005];
int n, a[100005], ans;
bool cmp(int a, int b) { 
	return a > b;
}
int main() { 
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i]; 
	for(int i = 1; i <= n; i++) {
		int pos = (int)(upper_bound(dp + 1, dp + 1 + n, a[i], cmp) - dp);
		//这是最长不上升子序列，改为lower_bound就是最长下降子序列。
        dp[pos] = a[i];
    }
	for(int i = 0; i < 100005; i++) dp[i] = 2147483647; 
	for(int i = 1; i <= n; i++) {
		int pos = (int)(upper_bound(dp + 1, dp + 1 + n, a[i]) - dp);
		//这是最长不下降子序列，改为lower_bound就是最长上升子序列。
        dp[pos] = a[i];
    }
	for(int i = 1; i <= n; i++) { 
		if(dp[i] == 2147483647) break; 
		ans++;
	}
	cout << ans << endl; 
	return 0;
}

这个问题的状态转移方程真的超级超级好懂了。直接上代码吧。

#include  
#include  
using namespace std;
int dp[1005][1005];
int n, m, a[1005], b[1005];
int max(int a, int b) { 
	if(a > b) return a;
	else return b; 
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i]; 
	for(int i = 1; i <= m; i++) cin >> b[i]; 
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(a[i] == b[j]) 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; 
}

但如果是 1 1 1~ n n n的某种排列的公共子序列，那可以让第二个序列对应第一个序列映射后求第二个序列的 L I S LIS LIS

L I S LIS LIS：最长上升子序列。

划分数就是有 n n n个无区别的物品，将它们划分成不超过 m m m组， 求出划分方法模 M M M的余数。

#include  
using namespace std;
int dp[1005][10005]; 
int n, m, M;
int main() {
	cin >> n >> m >> M;
	dp[0][0] = 1;
	for(int i = 1; i <= m; i++) {
		for(int j = 0; j <= n; j++) { //j的i划分 
			if(j - i >= 0) dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % M; 
			else dp[i][j] = dp[i - 1][j];
		} 
	}
    cout << dp[m][n] << endl;
}

#include  
using namespace std;
int dp[1005][10005]; 
int a[1005];
int n, m, M;
int main() {
	cin >> n >> m >> M;
	for(int i = 1; i <= n; i++) cin >> a[i]; 
	for(int i = 0; i <= n; i++) dp[i][0] = 1; 
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) { 
			if(j - a[i] > 0)
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1 - a[i]] + M) % M;
			else dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % M; 
		}
	}
    cout << dp[m][n] << endl;
}

Luogu P1048 [NOIP2005 普及组] 采药

01背包指的就是，我们有一个背包，然后有许多物品。背包是有一定的空间限制的，而每一个物品有相应的体积和价值。解决的问题就是在背包空间允许的范围内，背包所装的物品价值最大是多少。（好像做贼）

01背包的状态转移方程还是很简单的，无非就是选或者不选的问题。第 i i i个物品由第 i − 1 i-1 i−1个物品转移而来，选或不选当然是要选价值最大的。

状态转移方程如下：

d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − t [ i ] ] + w [ i ] ) dp[i][j] = max(dp[i-1][j],dp[i-1][j-t[i]]+w[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−t[i]]+w[i])

在这其中， t [ i ] t[i] t[i]表示这个物品所占的背包空间，在这个例题里就是采药所需要花的时间。而 w [ i ] w[i] w[i]表示的就是这个物品的价值，在这个题里就是药草的价值。 d p [ ] [ ] dp[][] dp[][]则表示这种方案的最大价值。

我觉得还是相当好理解的。 i i i表示第几个物品， j j j则表示还剩下的背包空间（在例题里就是还剩下多少时间）。 m a x max max函数里面有两项，第一项就是不选第 i i i个物品，所以背包空间不会发生变化，价值也不会变；第二项就是选择这个物品，把这个东西放进背包里，背包空间就会减小，而这种方案的价值就会增大。

下面的代码是已经压掉一维的代码。仔细想一下也可以知道，价值倒着来的话，实际上也就不需要第一维数组了，可以节省空间。

#include  
#include  
using namespace std;
int T, M, w[1005], t[1005]; 
int dp[1005];
int max(int a, int b) { 
	if(a > b) return a;
	else return b; 
}
int main() {
	cin >> T >> M;
	for(int i = 1; i <= M; i++) cin >> t[i] >> w[i]; 
	for(int i = 1; i <= M; i++)
		for(int j = T; j >= t[i]; j--)
			dp[j] = max(dp[j], dp[j - t[i]] + w[i]);
    cout << dp[T] << endl;
	return 0; 
}

Luogu P1616 疯狂的采药

每个东西不一定只能拿一个了！

如果不压掉维度的话，状态转移方程就是：

d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − k ∗ t [ i ] ] + k ∗ w [ i ] ) dp[i][j]=max(dp[i-1][j-k*t[i]]+k*w[i]) dp[i][j]=max(dp[i−1][j−k∗t[i]]+k∗w[i])

k = 0 , 1 , 2 , … k=0,1,2,… k=0,1,2,…

所以不同点就在于要枚举 k k k值。

压掉一维的写法上与01背包区别就只是循环顺序的不同。

#include  
#include  
using namespace std;
int T, M, w[1005], t[1005]; 
int dp[1005];
int max(int a, int b) { 
	if(a > b) return a;
	else return b; 
}
int main() {
	cin >> T >> M;
	for(int i = 1; i <= M; i++) cin >> t[i] >> w[i]; 
	for(int i = 1; i <= M; i++)
		for(int j = t[i]; j <= T; j++)
			dp[j] = max(dp[j], dp[j - t[i]] + w[i]);
    cout << dp[T] << endl;
	return 0; 
}

一般是三重循环，第一个是枚举长度，第二个枚举起点，第三个枚举切割点

也就是：

d p [ j ] [ j + i − 1 ] = m a x ( d p [ j ] [ k ] + d p [ k + 1 ] [ j + i − 1 ] + w [ i ] [ j + i − 1 ] , d p [ j ] [ j + i − 1 ] ) dp[j][j + i - 1] = max(dp[j][k] + dp[k + 1][j + i - 1] + w[i][j + i - 1], dp[j][j + i - 1]) dp[j][j+i−1]=max(dp[j][k]+dp[k+1][j+i−1]+w[i][j+i−1],dp[j][j+i−1])

CF607B Zuma

#include 
#include 
using namespace std;

int dp[505][505];
int n, c[505];
int min(int a, int b) {
    if(a < b) return a;
    else return b;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dp[i][j] = 2147483647;
    for(int i = 1; i <= n; i++) dp[i][i] = 1;
    for(int i = 1; i < n; i++) {
        if(c[i] == c[i + 1]) dp[i][i + 1] = 1;
        else dp[i][i + 1] = 2;
    }
    for(int l = 3; l <= n; l++) {
        for(int i = 1; i + l - 1 <= n; i++) {
            int j = i + l - 1;
            if(c[i] == c[j]) dp[i][j] = dp[i + 1][j - 1];
            for(int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

Luogu P1433 吃奶酪

#include 
#include 
#include 
#include 
using namespace std;

double xx[20], yy[20], ans;
double a[20][20];
double dp[20][34000];

double min(double a, double b) {
    if(a < b) return a;
    else return b;
}

int n;

double distan(int x, int y) {
    return sqrt((xx[x] - xx[y]) * (xx[x] - xx[y]) + (yy[x] - yy[y]) * (yy[x] - yy[y]));
}

int main() {
    memset(dp, 127, sizeof(dp));
    ans = dp[0][0];
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> xx[i] >> yy[i];
    for(int i = 0; i <= n; i++)
        for(int j = i + 1; j <= n; j++) {
            a[i][j] = distan(i, j);
            a[j][i] = a[i][j];
        }
    for(int i = 1; i <= n; i++) dp[i][1 << (i - 1)] = a[0][i];
    for(int s = 1; s < (1 << n); s++) {
        for(int i = 1; i <= n; i++) {
            if(!(s & (1 << (i - 1)))) continue;
            for(int j = 1; j <= n; j++) {
                if(!(s & (1 << (j - 1)))) continue;
                if(i == j) continue;
                dp[i][s] = min(dp[i][s], dp[j][s - (1 << (i - 1))] + a[i][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++)
        ans = min(ans, dp[i][(1 << n) - 1]);
    printf("%.2lfn", ans);
    return 0;
}

Luogu P1352 没有上司的舞会

#include 
using namespace std;

int n, root;
int r[6001], dp[6001][2], son[5001][5001], cnt[6001], tmpa, tmpb;
bool fla[6001];

int max(int a, int v) {
    if(a > v) return a;
    else return v;
}

void f(int x) {
    dp[x][0] = 0;
    dp[x][1] = r[x];
    for(int i = 1; i <= cnt[x]; i++) {
        f(son[x][i]);
        dp[x][0] += max(dp[son[x][i]][0], dp[son[x][i]][1]);
        dp[x][1] += dp[son[x][i]][0];
    }
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> r[i];
    for(int i = 1; i <= n - 1; i++) {
        cin >> tmpa >> tmpb;
        son[tmpb][++cnt[tmpb]] = tmpa;
        fla[tmpa] = true;
    }
    for(int i = 1; i <= n; i++) {
        if(!fla[i]) {
            root = i;
            break;
        }
    }
    f(root);
    cout << max(dp[root][0], dp[root][1]);
    return 0;
}