记忆化动态规划学习笔记
1.记忆化搜索与动态规划
01背包问题1
n的物品都有自己的wi，vi，背包最多可装载的重量为W，背包里的物体价值最大(1<<n<<100,1<=W<=10000,1<=wi,vi<=100
暴力写法，存在较多的重复计算，复杂度O（pow（2，k））
从第i个物品挑选总重小于j的部分
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;
}
记忆化搜索,复杂度O（nw）nw为参数组合数量
int sovle(int i, int j) {
//记忆化保存
if (dp[i][j] > 0)return dp[i][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 dp[i][j] = res;
}
定义：dp[i+1][j]:从0到i(i+1个)物品中选出总重量不超过j的最大物品的价值和。(假设物体从第0个开始)
1.dp[0][j]=0 (dp[i][0]=0如果物品价值都大于0）
2.dp[i+1][j]=dp[i][j] (j<w[i])
dp[i+1][j]=max{dp[i][j],dp[i][j-w[i]]+v[i]}
写法如下：i逆向进行也可以,此处不写
void solve() {
for(int i=0;i<n;i++)
for (int j = 0; j <= W; j++) {
if (j<w[i])dp[i + 1][j] = dp[i][j];
else dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
应用：最长公共子序列(Longest Common Subsequence)
定义：dp[i][j]:两个子序列分别到i和j的位置的LCS
状态转移如下：
dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])(s[i+1]!=s[j+1])
dp[i+1][j+1]=dp[i][j]+1(其他)
void solve() {
for(int i=0;i<n;i++)//此处不需要=
for (int j = 0; j <m; j++) {
if (s[i] == t[i])dp[i + 1][j + 1] = dp[i][j] + 1;
else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
}
}
2.进一步探索
完全背包问题
n的物品都有自己的wi，vi，背包最多可装载的重量为W，怎样使得背包里的物体的价值最大，每个物品可以选择任意多(1<<n<<100,1<=W<=10000,1<=wi,vi<=100
思考一下，首先我们可能会想到枚举k（k为每个物品选择的个数，现在就存在一个三重循环）进一步思考，由于每个物品可以选择任意多，当我们停留在选择某个物品上面，只有状态j会发生改变，所以转态转移如下
定义：dp[i+1][j]:从0到i(i+1个)物品中选出总重量不超过j的最大物品的价值和。(假设物体从第0个开始)
1. dp[0][j]=0 (dp[i][0]=0如果物品价值都大于0）
2.dp[i+1][j] (j<w[i])
dp[i+1][j]=max{dp[i][j],dp[i+1][j-w[i]]+v[i]}
写法于上面类似
void solve() {
for(int i=0;i<n;i++)
for (int j = 0; j <= W; j++) {
if (v[i] > j)dp[i + 1][j] = dp[i][j];
else dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
}
}
01背包和完全背包重复利用数组的情况
void solve() {
for(int i=0;i<n;i++)
for (int j = W; j >=w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
void solve() {
for(int i=0;i<n;i++)
for (int j = w[i]; j<=W; j++) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
dp[i + 1][j] = max(dp[i][j], dp[i+1][j - w[i]] + v[i])这种情况计算[i+1][j]时候只用到[i]和[i+1]，所以可以用到滚动数组，具体见白书。
01背包问题2
n的物品都有自己的wi，vi，背包最多可装载的重量为W，怎样使得背包里的物体的价值最大1<<n<<100,1<=W<=1e9,1<=wi<=1e7,1<=vi<=100
对于这个问题，相比之前的01背包，只是修改了限制条件的大小，之前的复杂度为O（nW），这个复杂度对于现在的规模是不够用了的，但是价值的范围较小，我们可以改变dp的对象。
定义：
dp[i+1][j]:前i个物品挑选总价值为J的最小总重量（不存在是为INF）。
dp[0][0]=0
dp[0][j]=INF
前i个物品挑选总价值为j状态可以由前i-1个物品挑选总价值为j的状态和前前i-1个挑选总价值为j-v[i]的状态转移而来。于是：
dp[i+1][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
最终的答案就是dp[n][j]<=W的最大j值。
时间复杂度为O（n*sigma(vi)）,这种题就是要根据问题规模来设定算法的对象。
int solve() {
//设立初状态
//N表示n的最大值，V表示总价值的最大
fill(dp[0], dp[0] + N * V + 1, INF);
dp[0][0] = 0;
for(int i=0;i<n;i++)
for (int j = 0; j < N*V; j++) {
if (j < v[i])dp[i + 1][j] = dp[i][j];
else dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
}
int res = 0;
for (int i = 0; i <= N * V; i++)if (dp[n][i] <= W)res = i;
return res;
}
多重部分和问题
有n个大小不同的数字ai，每个数字有mi个，判断能否从中选择部分使得他们的和为K（1<=n<=100,1<=ai,mi<=1e5,1<=K<=1e5）
定义dp[i+1][j]:对于前i个数字加和得到j时，第i个数字的最多剩余（不能加和得到j的情况为-1）
dp[i+1][j]=m[i](dp[i][j]>=0,前i-1个数字已经加和得到j，此时第i个数字不需要加入)
=-1(j<ai,or,dp[i+1][j-ai]<=0说明不管是否加入，都不能得到j)
=dp[i+1][j-ai]-1(其他情况)
重复利用数组，还是有点不太清晰。
void solve() {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for(int i=0;i<n;i++)
for (int j = 0; j <= K; j++) {
if (dp[j] >= 0)dp[j] = m[i];
else if (j < a[i] || dp[j - a[i]] <= 0)dp[j] = -1;
else dp[j] = dp[j - a[i]] - 1;
}
}
最长上升子序列（Longest Increasing Subsequence）
在一个长为n的数列中（a0,a1,a2,a3...,an-1）。请你求出最长的上升子序列长度。（1<=n<=1000,0<=ai<=1000000）
定义dp[i]:以a[i]为结尾的最长上升子序列长度。
dp[i]=max{1, dp[j]+1|j<i&&aj<ai}
int n;
int a[MAX_N];
int dp[MAX_N];
void solve(){
int res=0;
for(int i=0;i<n;i++){
dp[i]=1;
for(int j=0;j<i;j++)
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1)
}
res=max(res,dp[i]);
}
cout<<res<<endl;
}