![[Acwing] 算法汇总五 动态规划 一](http://www.mshxw.com/aiimages/31/879295.png "[Acwing] 算法汇总五 动态规划 一")
- 背包问题
- 01背包问题
- 完全背包
- 多重背包问题 I
- 多重背包问题 II
- 分组背包
- 线性DP
- 最长上升子序列
- 最长上升子序列 II
- 最长公共子序列
- 最短编辑距离
- 编辑距离
- 区间DP
- 石子合并
状态表示 :
f
[
i
]
[
j
]
f[i][j]
f[i][j] 前
i
i
i个物品中,体积为
j
j
j的最大价值
状态转移 :
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
(
j
−
v
<
0
)
f[i][j] =f[i-1][j](j-v<0)
f[i][j]=f[i−1][j](j−v<0)
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
−
1
]
[
j
]
,
f
[
i
−
1
]
[
j
−
v
]
+
w
[
i
]
)
f[i][j] =max(f[i-1][j],f[i-1][j-v]+w[i])
f[i][j]=max(f[i−1][j],f[i−1][j−v]+w[i])
因为我们每次用到的都是第二层的状态,第一层的状态一直没有用到
因此我们可以考虑优化掉第一层
但是因为 f [ i ] [ j ] f[i][j] f[i][j]与 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]独立
因此我们需要倒序处理
完全背包每个物品可以无限用
因为存在无限用的规则,因此有一个暴力写法就是枚举
k
∗
v
[
i
]
<
m
k*v[i] 不过可想而知这是
n
3
n^3
n3的 我们由下列等式可知
f
[
i
,
j
−
v
]
=
m
a
x
(
f
[
i
−
1
,
j
−
v
]
,
f
[
i
−
1
,
j
−
2
∗
v
]
+
w
,
f
[
i
−
1
,
j
−
3
∗
v
]
+
2
∗
w
,
.
.
.
.
.
)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
f[i,j−v]=max(f[i−1,j−v],f[i−1,j−2∗v]+w,f[i−1,j−3∗v]+2∗w,.....) 第三层循环没必要,则转移过程变为 因为这里只用到了第
i
i
i层,因此我们可以反着和
01
01
01背包问题优化 我们只需要正向枚举进行转移即可 将多重背包的各个价值,看作多个价值,然后跑一遍
01
01
01背包 即可 将多重背包进行二进制拆分 有多个组,每组有多个物品,每组只能选一个 因此属于是
01
01
01背包的嵌套 状态表示 : 因为只用到了第
i
−
1
i-1
i−1层,所以考虑使用
01
01
01背包倒序优化 从上和从下进行转移 但是需要处理边界,对于外围边界都是
−
I
N
F
-INF
−INF 状态表示 : 状态计算 : 模板 状态表示 : 状态计算 : 询问字符串
A
A
A经过最少次操作之后变为
B
B
B 操作定义如下 : 状态表示 : 状态计算 : 当然显然的,对于初始化所有的
i
i
i 显然对于每个字符串之间的转换最优的选择都是选择最短编辑距离,同时又因为时间复杂度支持,因此我们可用完全套用上面的模板 给定
N
N
N堆石子,每次合并相邻的两堆,对于每次合并都会消耗
a
[
i
]
+
a
[
j
]
a[i]+a[j]
a[i]+a[j],询问最小的代价 关键点 : 状态表示 : 状态计算 : 显然初始化
f
[
i
]
[
i
]
=
0
f[i][i]=0
f[i][i]=0 当然对于处理 区间dp方法也很特殊 枚举长度+左端点,然后枚举切分
f
[
i
,
j
]
=
m
a
x
(
f
[
i
−
1
,
j
]
,
f
[
i
−
1
,
j
−
v
]
+
w
,
f
[
i
−
1
,
j
−
2
∗
v
]
+
2
∗
w
,
f
[
i
−
1
,
j
−
3
∗
v
]
+
3
∗
w
,
.
.
.
.
.
)
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i,j]=max(f[i−1,j],f[i−1,j−v]+w,f[i−1,j−2∗v]+2∗w,f[i−1,j−3∗v]+3∗w,.....)
得出
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
,
j
−
v
]
+
w
,
f
[
i
−
1
]
[
j
]
)
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
f[i][j]=max(f[i,j−v]+w,f[i−1][j])
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
f
[
i
]
[
j
−
v
]
+
w
[
i
]
)
f[i][j]=max(f[i][j],f[i][j-v]+w[i])
f[i][j]=max(f[i][j],f[i][j−v]+w[i]) for(int i = 1 ; i<=n ;i++)
for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
多重背包问题 I
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=s[i]&&k*v[i]<=j;k++)
f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);
}
}
cout<void solve()
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
int v,w,s; cin>>v>>w>>s;
for(int k = 1;k<=s;k*=2)//二进制拆分
{
for(int j = m;j>= k*v;j--)
f[j] = max(f[j],f[j-k*v]+k*w);
s-=k;
}
if(s)
{
for(int j = m ;j>=s*v;j--)
{
f[j] = max(f[j],f[j-s*v]+s*w);
}
}
}
cout<
f
[
i
]
[
j
]
f[i][j]
f[i][j] 从前
i
i
i组物品选,体积小于等于
j
j
j的最大值
状态计算 :
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
f[i][j] =f[i-1][j]
f[i][j]=f[i−1][j]
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
f
[
i
−
1
]
[
j
−
v
[
i
]
[
k
]
]
+
w
[
i
]
[
k
]
]
)
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]])
f[i][j]=max(f[i][j],f[i−1][j−v[i][k]]+w[i][k]])#include
const int N = 500+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;
struct node{
int to,val;
};
int a[N][N];
int n;
int f[N][N];
void solve(){
memset(f,-0x3f,sizeof f);
int n;cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
f[i][j] = a[i][j];
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j] += max(f[i-1][j],f[i-1][j-1]);
}
}
int ans = -INF;
for(int i=1;i<=n;i++)
ans = max(f[n][i],ans);
cout<
f
[
N
]
f[N]
f[N]以当前
i
i
i结尾的最大上升子序列长度
我们
N
2
N^2
N2的枚举
a
[
j
]
<
a
[
i
]
a[j]a[j]int f[N];
int a[N];
int n;
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
f[i] =1 ;
for(int j = 1; j< i ;j ++ ){
if(a[j] < a[i]) f[i] = max(f[i],f[j]+1);
}
}
int ans = -INF;
for(int i=1;i<=n;i++) ans = max(ans,f[i]);
cout<
或者二分的寻找最大的小于
a
[
i
]
a[i]
a[i]的位置进行转移int main(void) {
int n; cin >> n;
vector
最长公共子序列
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示
a
a
a中的前
i
i
i个字母和
b
b
b中的前
j
j
j个字母的最长公共子序列长度
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
−
1
]
[
j
−
1
]
,
f
[
i
−
1
]
[
j
−
1
]
,
f
[
i
−
1
]
[
j
]
,
f
[
i
−
1
]
[
j
−
1
]
+
1
)
f[i][j]=max(f[i-1][j-1],f[i-1][j-1],f[i-1][j],f[i-1][j-1]+1)
f[i][j]=max(f[i−1][j−1],f[i−1][j−1],f[i−1][j],f[i−1][j−1]+1)int main()
{
cin>>n>>m;
cin>>a+1>>b+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j] = max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])
f[i][j]= max(f[i][j],f[i-1][j-1]+1);
}
}
cout<
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示
a
a
a中的前
i
i
i个变为
b
b
b中的前
j
j
j个字母的操作次数
f
[
i
]
[
j
]
=
f
[
i
]
[
j
−
1
]
+
1
f[i][j] =f[i][j-1]+1
f[i][j]=f[i][j−1]+1添加一个字母
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
1
f[i][j]=f[i-1][j]+1
f[i][j]=f[i−1][j]+1删除一个字母
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
1
]
+
1
f[i][j]=f[i-1][j-1]+1
f[i][j]=f[i−1][j−1]+1替换该字母,因为我们替换的是最后面的那个字母,所有应该从
i
−
1
,
j
−
1
i-1,j-1
i−1,j−1转移过来
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
1
]
f[i][j]=f[i-1][j-1]
f[i][j]=f[i−1][j−1]什么也不做
f
[
0
]
[
i
]
=
i
f[0][i]=i
f[0][i]=i同时
f
[
i
]
[
0
]
=
i
f[i][0]=i
f[i][0]=i scanf("%d%s", &n, a + 1);
scanf("%d%s", &m, b + 1);
for (int i = 0; i <= m; i ++ ) f[0][i] = i;
for (int i = 0; i <= n; i ++ ) f[i][0] = i;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
printf("%dn", f[n][m]);
}
编辑距离
#include
区间DP
石子合并
最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示
i
i
i到
j
j
j这一段石子合并成一堆的最小花费
f
[
i
]
[
j
]
=
m
i
n
(
f
[
i
]
[
j
]
,
f
[
i
]
[
k
]
+
f
[
k
+
1
]
[
j
]
+
s
[
j
]
−
s
[
i
−
1
]
)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1])
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]−s[i−1]) int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
s[i] += s[i - 1] + a[i];
}
memset(f, 0x3f, sizeof f);
// 区间 DP 枚举套路：长度+左端点
for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素个数
for (int i = 1; i + len - 1 <= n; i ++) {
int j = i + len - 1; // 自动得到右端点
if (len == 1) {
f[i][j] = 0; // 边界初始化
continue;
}
for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= j
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n] << endl;
}
