浅谈动态规划
动态规划（DP，Dynamic Programming）是一种利用递推实现的算法，它的核心是一步一步的计算，记录结果，最后得到最终的答案。
最经典的DP问题 —— 背包问题
记忆化搜索与动态规划
我们可以用最简单的朴素的算法搜索来实现
// 只展示 solve 部分
int rec (int i, int j) {
int res;
if (i == n)
res = 0;
else if (j < w[i])
res = rec(i + 1, j);
else
res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
return res;
}
void solve() {
printf("%d\n", rec(0, W));
}
由于这种方法的深度是 $N$ , 每次进行 2 次分支后时间复杂度就是 $O(2^n)$，并不是最好的算法。
我们可以发现在调用这些函数的时候会有一些重复的计算被多次调用，导致了时间复杂度的增加。
如何才能减少这种重复的计算呢？
这里提供 记忆化搜索 进行优化。
使用 $f[i][j]$ 表示调用的值,对代码进行小小的修改
// 只展示 solve 部分
int f[MAX_N][MAX_N];
int rec (int i, int j) {
int res;
if (f[i][j])
retun f[i][j];
if (i == n)
res = 0;
else if (j < w[i])
res = rec(i + 1, j);
else
res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
return f[i][j] = res;
}
void solve() {
memset(f, -1, sizeof f);
printf("%d\n", rec(0, W));
}
这小小的改进会让最坏的情况减少为 $O(nW)$ ， 已经算是很快了。
使用 memset 按照 1 字节对单位进行填充，可填充的量为0， -1， 127， 128
大大提高初始化效率
同时还给出fill供读者自行百度
我们可以发现这个递归函数的记忆化数组的变化是可以用循环实现的
void solve () {
for (int i = n - 1; i ; i --) {
for (int j = 0; j <= W; j++) {
if(j < w[i])
f[i][j] = f[i + 1][j];
else
f[i][j] = max(f[i + 1][j], f[i + 1][j - w[i] +v[i]);
}
}
printf("%d\n", f[0][W]);
}
这个算法的复杂度和前面相同，都是 $O(nW)$, 却简洁了不少，这种一步步按照顺序从记忆化搜索数组出发所得到的答案的算法就是动态规划。
而动态规划的核心就是推导出递推式。
这一类题目十分灵活，用数组的不同结果代表答案，如果前面的出现错误，其他都会出现错误。
像上面那个代码其实还可以这样写
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j <= W; j++) {
f[i + 1][j] = max(f[i + 1][j], f[i][j]);
if (j + w[i] <= W)
f[i + 1][j + w[i]] = max(f[i + 1][j + w[i]], f[i][j] + v[i]);
}
}
printf("%d\n", f[n][W]);
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j <= W; j++) {
if (j < w[i])
f[i + 1][j] = f[i][j];
else f[i + 1][j] = max(f[i][j], f[i][j - w[i]] + v[i]);
}
}
printf("%d\n", f[n][W]);
}
都是可以的。
如果我们在进行深入研究就会发现这种情况都是由上一步的状态转移过来的。
我们可以通过奇偶性写下这样的代码
int f[2][MAX_W];
void solve() {
for (int i = 0; i < N; i++) {
for (int j = 0; j <= W; j++) {
if (j < w[i])
f[(i & 1)][j] = f[i & 1][j];
else
f[(i & 1)][j] = max(f[(i + 1) & 1][j], f[(i + 1) & 1][j - w[i]] + v[i]);
}
}
printf("%d\n",f[(N + 1) & 1][W]);
}
我们还可以将减少一维，只用一维数组 $f[i]$ 来表示当最大容量为 $i$ 的时候的最大答案。
void solve() {
for (int i = 0; i < n; i++)
for (int j = m; j >= w[i]; j--)
f[j] = max (f[j], f[j - w[i]] + v[i]);
printf("%d\n", f[W]);
}
这道题就可以解决了！
最长公共子序列
最长公共子序列（Longest Common Subsequence, LCS）,给定 2 个序列 $X$, $Y$, 找出 $X$ 和 $Y$ 的最长公共子序列。
我们使用 $DP$ 求解时间复杂度是 $O(nm)$
其中用 $f[i][j]$ 表示子序列 $ X_i $, $Y_i$ 的最长公共子序列的长度
inline void solve() {
int lena = strlen(a), lenb = strlen(b);
for (int i = 1; i <= lena; i++) {
for (int j = 1; j <= lenb; j++) {
if (a[i - 1] == b[j - 1])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
printf("%d\n", f[lena][lenb]);
}
背包九讲
先咕着，
资料
由于有依赖的背包涉及树型DP, 这里给出一种不用树的做法，但是每个主件只能有一个附件
计数DP | 划分DP
#include <bits/stdc++.h>
using namespace std;
const int N=5000;
int n,m,k;
int ans;
int f[N][N];
//j个元素在i个盘子里
int main(){
//n：苹果
//s: 盘子
scanf("%d%d",&n,&k);
//只有1个元素
for(int i=1;i<=n;i++)f[i][1]=1;
//DP
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(i<j){
f[i][j]=f[i][i];
}
if(i>j){
f[i][j]=f[i-j][j]+f[i][j-1];
}
if(i==j){
f[i][j]=f[i][j-1]+1;
}
}
}
printf("%d\n",f[n][k]);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=1000;
ll n,k;
ll ans;
int f[N][N],d[N][N];
int main(){
scanf("%lld",&n);
f[0][0]=d[0][0]=1;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=i;j++){
d[i][j]=f[i-j][j];
f[i][j]=f[i-1][j-1]+d[i-j][j];
d[i][j]%=MOD;
f[i][j]%=MOD;
}
}
for(ll i=1;i<=n;i++){
ans=(ans+f[n][i])%MOD;
}
printf("%lld",ans);
return 0;
}
// 即前面的放苹果。
坐标DP
#include<bits/stdc++.h>
using namespace std;
const int N=50+20;
int m,n,dp[N][N][N][N],aa[N*10][N*10];
int maxx(int a,int b,int c,int d){return max(a,max(b,max(c,d)));}
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>aa[i][j];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
for(int x=1;x<=m;x++){
for(int y=j+1;y<=n;y++){
if(x+y==i+j){
int a,b,c,d;
a=dp[i-1][j][x-1][y]+aa[x][y]+aa[i][j];
b=dp[i-1][j][x][y-1]+aa[x][y]+aa[i][j];
c=dp[i][j-1][x-1][y]+aa[x][y]+aa[i][j];
d=dp[i][j-1][x][y-1]+aa[x][y]+aa[i][j];
dp[i][j][x][y]=maxx(a,b,c,d);
}
}
}
}
}
cout<<dp[m][n-1][m-1][n];
return 0;
}