初级dp

发表于 |
字数统计: 1.6k | 阅读时长 ≈ 8

数塔问题：

思路：dp数组记录底层，然后每次上一层加上下一层两边的最大值就行了
转移方程：dp [ i ] [ j ] = max(dp[i+1][j] ,dp[i+1][j+1]) + f[i][j]
i 是倒序的，从n-1 到 1吧，然后每次j会<=i,回到1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//数塔问题：可以从第一层加至第五层，每次选一层一个数；
// 求路径上数字最大和
//   
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1010;
int f[maxn][maxn],dp[maxn][maxn];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>f[i][j];
		}
	}
	for(int i=1;i<=n;i++)
		dp[n][i]=f[n][i];
	//每次转移至上一层 
	for(int i=n-1;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
		}
	}
	cout<<dp[1][1]<<endl;
	return 0;	
}

最大连续子列和

思路：每次寻找最大添加该元素后的连续子序列，和当前序列本身
转移方程：dp[i] = max(a[i],dp[i-1]+a[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//最大连续子列和问题 
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1010;
int a[maxn],dp[maxn],n;
int main()
{
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dp[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		//状态转移方程
		//会等于前一段子序列，和添加当前子序列中的最大值 
		dp[i]=max(a[i],dp[i-1]+a[i]);
	}
	for(int i=1;i<=n;i++)
		ans=max(ans,dp[i]);
	cout<<ans<<endl;
	return 0;
}

连续不下降最长子序列LIS：

思路：每次让dp[i]的长度为1，然后判断a[i]是否大于a[j]，dp[j]+1是否大于dp[i]如果满足则进行转移，i表示以i结尾的子序列，所以j<i
转移方程：if a[i]>a[j] && dp[j]+1>dp[i] 则进行转移 dp[i]=dp[j+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//最长连续不下降子序列 
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1010;
int a[maxn],dp[maxn],n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int ans=-1;
	//i表示以i结尾的最长连续不下降子序列 
	for(int i=1;i<=n;i++)
	{
		dp[i]=1;
		for(int j=1;j<i;j++)
		{
			if(a[i]>=a[j] && dp[j]+1>dp[i])
				dp[i]=dp[j]+1;
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

最长公共子序列问题LCS：

思路：i表示s1串的前i个字母，j表示s2串的前j个字母，进行判断是有两种可能一种是 s1[i] == s2[j]，则dp[i+1][j+1]=dp[i][j]+1, 另一种是s1[i] != s2[j] 的情况，这种情况就是判断 dp[i+1][j] 和dp[i][j+1] 的大小，等于之间较大的这样转移方程就出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//最长公共子序列问题
// 比如sadstory
// adminsorry
// 的最长公共子序列为adsory 

#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1010;
int dp[maxn][maxn];
int main()
{
	string s1;
	string s2;
	cin>>s1;
	cin>>s2;
//  idea：两个分枝：
//	当s1[i]==s2[j] 时，长度直接为上一个加一即可 
//  当不等于时 ，判断 dp[i-1][j] 和 dp[i][j-1]之间的大小，大的连接作为最长的子序列 
	for(int i=0;i<s1.size();i++)
	{
		for(int j=0;j<s2.size();j++)
		{//每次都同时延长一个长度 
			if(s1[i]==s2[j])
			{
				dp[i+1][j+1]=dp[i][j]+1;
			}
			else{
				dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
			}
		}
	}
	cout<<dp[s1.size()][s2.size()]<<endl;
	return 0;
}

背包问题大合集：

01 背包
注意for的顺序
for i = 0:n-1
for j = W:w[i]
状态转移方程 dp[j] = max(dp[j],dp[j-w[i]]+v[i]);

完全背包问题
for i = 0:n-1
for j = w[i]:W
状态转移方程 dp[j] = max(dp[j],dp[j-w[i]]+v[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1010;
int n,W;
int dp[maxn][maxn];
int w[maxn],v[maxn];
int ddp[maxn];

//o1背包思路
//	 i表示放第i件物品
//	 策略1，不放第i件物品则dp[i+1][j]=dp[i][j];
//	 策略2，放第i件物品，然后dp[i+1][j]转换成了前dp[i][j]和dp[i][j-w[i]]+v[i]最大值; 
void solve01_dp()
{
	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]);
			}
		}
	}
	cout<<dp[n][W]<<endl;
}


//完全背包，一件物品可放多次 
//此方法不是很建议，复杂度有点高，但可以优化 
void solve_all_dp()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=W;j++)
		{
			for(int k=0;k*w[i]<=j;k++)
				dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
		}
	}
	cout<<dp[n][W]<<endl;
}

//完全背包优化版与01背包不同之处在于
// 转换dp[i+1][j]放是判断dp[i][j]和dp[i+1][j-w[i]]+v[i]的大小，后面变成了i+1
// 因为可以多放几次 
void solve_all_dp2()
{
	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+1][j-w[i]]+v[i]);
			}
		}
	}
}


//	01背包1维数组版
// 	注意是逆序枚举j 
void solve__01dp()
{
	for(int i=0;i<n;i++)
	{
		for(int j=W;j>=w[i];j--)
			ddp[j]=max(ddp[j],ddp[j-w[i]]+v[i]);
	}
	cout<<ddp[W]<<endl;
}

// 完全背包，顺序枚举j
// 状态转移格式都是 dp[j] = max(dp[j],dp[j-w[i]]+v[i]) 
void solve__alldp()
{
	for(int i=0;i<n;i++)
	{
		for(int j=w[i];j<=W;j++)
			ddp[j]=max(ddp[j],ddp[j-w[i]]+v[i]);
	}
	cout<<ddp[W]<<endl;
}

int max_n,max_v;
//o1dp的衍生问题，当w特别大时

//idea:两个分枝：
//前i-1个物品挑选价值总和为j的部分 
//前i-1个物品j-v[i]的部分，然后再选中第i个物品 
void dp01()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<==max_n*max_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<=max_n*max_v;i++) if(dp[n][i]<=w) res=i;
	 cout<<res<<endl;
 } 
int main()
{
	return 0;
}
-------------本文结束感谢您这么好看还看我的文章-------------