C++DP的学习笔记

一、动态规划基础概念

定义：动态规划（Dynamic Programming，简称 DP）是一种解决多阶段决策问题的数学优化方法。它将原问题分解成若干个子问题，通过解决子问题并将结果保存下来，避免重复计算，提高算法效率。

二、适用问题特点

1.最优子结构：问题的最优解所包含的子问题的解也是最优的，局部最优解能决定全局最优解。

2.子问题重叠：子问题被重复求解，如斐波那契数列中，计算F(n)时，F(n-1)和F(n-2)等子问题会被多次计算。

三、动态规划解题步骤

1.确定 dp 数组及下标的含义：明确dp数组用来存储什么信息，以及数组下标的意义。例如在背包问题中，dp[i][j]可能表示前i个物品放入容量为j的背包中所能获得的最大价值。

2.确定状态转移方程：这是动态规划的关键，找到如何通过已知子问题的解推导出当前问题的解。比如在 01 背包问题中，dp[i][j] = max(dp[i-1][j-w[i]] + c[i], dp[i-1][j])。

3.dp 数组初始化：根据问题的边界条件，给dp数组赋初值。如在 01 背包中，dp[0][j] = 0表示没有物品时，无论背包容量多大，价值都为 0。

4.确定遍历顺序：确定是先遍历物品还是先遍历背包容量等，不同的问题有不同的合适遍历顺序。如 01 背包通常先遍历物品，再遍历背包容量，且背包容量要倒序遍历。

四、动态规划常见类型

1.斐波那契数列类型：包括斐波那契数列、爬楼梯、最小费用爬楼梯、泰波那契数、打家劫舍等。

2.矩阵类型题：最小路径和、不同路径、下降路径最小和、最大正方形等。

3.背包问题：01 背包、01 背包滚动数组、分割等和子集、零钱兑换、一和零等。 4.子序列问题：最长上升子序列、最长增长子序列、最长连续递增子序列、最长公共子序列、最长回文子串、编辑距离、单词拆分等。

5.股票问题：买卖股票最佳时机系列，包括买卖一次、买卖多次、买卖两次、买卖多次有手续费、买卖多次有冻结时间等。

五、动态规划与其他算法思想的区别

与分治思想

相似点：都能将问题分解为子问题求解。 不同点：动态规划解决的问题有重复子问题，且用于求解最优化问题；分治问题不一定有重复子问题，也不一定是最优化问题。

与贪心思想

相似点：都能分解为子问题求解。 不同点：贪心基于最优化策略，由局部最优推全局最优，需证明策略正确性；动态规划求得的一定是最优解，无需证明。

题型

一维dp

1.dp求最大子序列和：

例：输入n(n<=100000)，和n个数，求序列中的最大子段和。

#include<bits/stdc++.h>
using namespace std;
int n,a,f[100001],maxn;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		if(i==1)f[1]=a;
		else f[i]=max(f[i-1]+a,a);
		maxn=max(maxn,f[i]);
	}
	cout<<maxn;
} 

2.dp求最大子序列积：

输入一个整数n，和一个序列a，求它的最大子序列和。

#include<bits/stdc++.h>
using namespace std;
int n,a,f[100001],g[100001],maxn;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		if(i==1)f[1]=g[1]=a;
		else{
			f[i]=max(f[i-1]*a,max(g[i-1]*a,a));
			g[i]=min(g[i-1]*a,min(f[i-1]*a,a));
		}
		maxn=max(maxn,f[i]);
	}
	cout<<maxn;
} 

3.dp求最长不下降子序列

#include<bits/stdc++.h>
using namespace std;
int n,a[100001],f[100001],maxn;
int main(){
	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);
		}
		maxn=max(maxn,f[i]);
	}
	cout<<maxn;
}

二维dp

1.最长公共子序列

#include<bits/stdc++.h>
using namespace std;
int f[1001][1001];
string s1,s2;
int main(){
	cin>>s1>>s2;
	int x=s1.size(),y=s2.size(); 
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++){
			if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1]+1;
			else f[i][j]=max(f[i-1][j],f[i][j-1]);
		}
	}
	cout<<f[x][y];
}

背包dp

1.01背包

有一个容量为p的背包，有n个物品，每个物品的重量为w[i]，价值为v[i]。如何放置物品是背包。

#include<bits/stdc++.h>
using namespace std;
int n,p,w[1001],v[1001],f[100001];
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++){
		for(int j=p;j>=w[i];j--){
			f[j]=max(f[j-w[i]]+v[i],f[j]); 
		}
	}
	cout<<f[p];
}

2.满背包

#include<bits/stdc++.h>
using namespace std;
int n,p,v[10001];
bool f[100001]={true};
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=n;i++){
		for(int j=p;j>=v[i];j--){
			f[j]|=f[j-v[i]];
		}
	}
	if(f[p])cout<<"true";
	else cout<<"false";
}

3.多重背包

#include<bits/stdc++.h>
using namespace std;
int n,p,w[1001],v[1001],c[1001],f[100001];
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++)cin>>c[i]>>w[i]>>v[i];
	for(int i=1;i<=n;i++){
		for(int j=p;j>=0;j--){
			for(int k=1;k<=min(c[i],p/w[i]);k++){
				if(j>=k*w[i])f[j]=max(f[j],f[j-k*w[i]]+k*v[i]); 
			} 
		} 
	}
	cout<<f[p];
}

4.完全背包

#include<bits/stdc++.h>
using namespace std;
int n,p,w[1001],v[1001],f[100000];
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=p;j++){
			f[j]=max(f[j-w[i]]+v[i],f[j]);
		}
	}
	cout<<f[p];
}