dp总结（未完）

动态规划
对于一个能用动态规划解决的问题，一般采用如下思路解决：
1.将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
2.寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3.按顺序求解每一个阶段的问题。
4.能用dp解决的问题需要有三个要素：最优子结构，无后效性和子问题重叠。
列1：背包问题
[NOIP2005 普及组] 采药

问题：总共有 \(M\) 个草药，每个草药得价值为 \(v\) ，每采一个草药需要花 \(t\) 个时间，要求要在一个固定时间 \(T\) 内使采得的药物总价值最大。

方法1：dfs暴力搜索
解法：一个一个往前摸
完整代码：

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+10;
int t[N],v[N],ans;
int T,M;

void dfs(int sumv,int pos,int sumt){
	if(sumt>T) return ;
	if(pos==M) {
		ans=max(ans,sumv);
		return ;
	}
	dfs(sumv+v[pos],pos+1,sumt+t[pos]);
	dfs(sumv,pos+1,sumt);//回溯
}

int main(){
	cin>>T>>M;
	for(int i=0;i<M;i++){
		cin>>t[i]>>v[i];
	}
	dfs(0,0,0);
	cout<<ans;
	return 0;
}

结过：超时，时间复杂度为 \(O(2^N)\) 级别。

方法2：dp（动态规划）
解法：
1.不摘草药
时间不变，把前面得状态复制过来,

dp[i][j]=dp[i-1][j];

2.采摘草药
当前时间减去该草药所需得时间，并且加上该草药的价值，

dp[i][j]=dp[i-1][j-t[i]]+v[i];

然后进行比较

dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);

完整代码：

#include <bits/stdc++.h>
using namespace std;

int t[1001],v[101],dp[1001][1001];  

int main(){
	int T,M;
	cin>>T>>M;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>v[i];
	} 
	for(int i=1;i<=T;i++){ 
		for(int j=1;j<=M;j++){ 
			if(j>=t[i]){
				dp[i][j]=max(dp[i-1][j-t[i]]+v[i],dp[i-1][j]);
			}
			else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[M][T];
	return 0;
}

结过：AC