动态规划

发表于 | 更新于 
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
1.KMP
/*KMP算法 
查询字符串a中 是否包含 字符串b    
ababcabcacbab
abcac
*/
    
void getNext(string str) {
	int k = 0;
	for (int i = 1; i < str.size(); i++) {
		while (k > 0 && str[i] != str[k])
			k = next[k-1];                               //精髓
		if (str[i] == str[k]) k++;
		next[i] = k;
	}
} 

int kmp(string s1, string s2) {
	int i = 0, j = 0;
	for (i = 0; i < s1.size() && j < s2.size(); i++) {
		 if (s1[i] == s2[j]) {
		 	j++;
		 } else {
		 	j = next[j-1];                          //需要感受
		 }
	}
	if (j == s2.size()) return i - s2.size();          //返回第一次匹配的的下标
	return -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
36
37
38
39
40
41
42
43
44
45
46
47
48
2.背包问题  
//     01背包问题  
// f[i][j]代表了 前i个物品的时候 容量为j的时候的最大的价值量，其中j必须是从v ...0的，因为每一个物品要选一次！！！ 

{
	
	int m,n;                 //m:背包的容量 n:物品的个数 
	cin>>m>>n; 
	int w[n+10];			   //每个物品的重量 
	int c[n+10];				//每个物品的价值 
	int f[m+10];             //f[k]代表 k个物品的时候，能装的最大的价值 
	memset(f,0,sizeof(f));
	for(int i=0; i<n; i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=0; i<n; i++)
	{
		for(int v = m; v>=w[i]; v--)
		{
			f[v] = max(f[v],f[v-w[i]] + c[i]);
		}	
	} 
	cout<<f[m]<<endl;		
}


//完全背包问题
{
	int m,n;                 //m:背包的容量 n:物品的个数 
	cin>>m>>n; 
	int w[n+10];			   //每个物品的重量 
	int c[n+10];				//每个物品的价值 
	int f[m+10];             //f[k]代表 k个物品的时候，能装的最大的价值 
	memset(f,0,sizeof(f));
	for(int i=0; i<n; i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=0; i<n; i++)
	{
		for(int v = w[i]; v<=m; v++)
		{
			f[v] = max(f[v],f[v-w[i]] + c[i]);
		}	
	} 
	cout<<f[m]<<endl;
}
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
3.最大上升 子序列 
/*给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4
*/

int fun(int a[],int n)
{
	int b[n];                    //截至到i 最大的上升子序列 的个数 
	for(int i=0; i<n; i++)
		b[i] = 1;
	for(int i=1; i<n; i++)
	{
		int max = -1;
		for(int j=0; j<i; j++)                        //找出前面比  此时的x 小的，并且 连续数最 大的   ~！！！ 
		{
			if(a[j] < a[i] && b[j] > max)
			{
				max = b[j];		
			}
		}
		if(max != -1)
			b[i] = max +1;
	}
	int maxx = 0;
	for(int i=0; i<n; i++)
		maxx = max(b[i],maxx);
	return maxx;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
最大子数组和
4.{
    int a[] = {1, -2, 3, -4, 5, 6, -7};
	int n = sizeof(a) / sizeof(int);
	int max = INT_MIN;
	int k = INT_MIN;
	for (int i = 0; i < n; i++) {
		if (k > 0) {
			k += a[i];	
		} else {
			k = a[i];
		}
		if (k > max) {
			max = k;
		}
	}    
  }