动态规划1-----------poj1080

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<iostream>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 /*dp，poj1080*/
 8 
 9 int dp[105][105];//动态规划数据存放
10 int map[105][105];//用来存放原始数据
11 
12 void map_init()
13 {
14     map['A']['A']=map['C']['C']=map['G']['G']=map['T']['T']=5;
15     map['A']['C']=map['C']['A']=map['A']['T']=map['T']['A']=map['T'][' ']=map[' ']['T']=-1;
16     map['A']['G']=map['G']['A']=map['C']['T']=map['T']['C']=map['G']['T']=map['T']['G']=map['G'][' ']=map[' ']['G']=-2;
17     map['A'][' ']=map[' ']['A']=map['G']['C']=map['C']['G']=-3;
18     map['C'][' ']=map[' ']['C']=-4;
19 }
20 
21 int max_X3(int a,int b,int c)
22 {
23     if(a>b)
24     {
25         if(a>c)
26             return a;
27         else
28             return c;
29     }
30     else
31     {
32         if(b>c)
33             return b;
34         else
35             return c;
36     }
37 }
38 
39 int    main()
40 {
41     int y;//全局次数
42     int i,j;//循环变量
43     int a,b;//用户输入
44     char str1[105]; 
45     char str2[105];
46 
47     //初始化
48     map_init();
49 
50     cin>>y;
51     while (y--)
52     {
53         scanf("%d %s",&a,str1);
54         scanf("%d %s",&b,str2);
55 
56         //初始化第一行第一列
57         dp[0][0]=0;
58         for (i = 0; i < a; i++)
59             dp[0][i+1] = dp[0][i] + map[str1[i]][' '];
60 
61         for (j = 0; j < b; j++)
62             dp[j+1][0] = dp[j][0] + map[str2[j]][' '];
63 
64         for (i = 1; i <= a; i++)
65         {
66             for (j = 1; j <= b; j++)
67             {
68                 dp[j][i] = max_X3(dp[j-1][i-1]+map[str2[j-1]][str1[i-1]], 
69                     dp[j-1][i]+map[str2[j-1]][' '],
70                     dp[j][i-1]+map[str1[i-1]][' ']);
71             }
72         }
73 
74         cout<<dp[b][a]<<endl;
75     }
76     return 0;
77 }

先上代码，然后说明。

首先对于动态规划到现在的理解，只是现阶段的理解。动态规划下面用dp代替。

要点：

1、一个问题可以被分成多个相同的子问题，子问题和原问题差别只有数据规模，总结就是大化小。

2、这个问题的解可以由子问题的解得出，总结就是用已经有的小解得出最后的解。

3、经常用一个二维数组去保存已经求出的解，之后要是用到就可以直接取不用计算，总结就是记录已经解过的方程的解，不做相同的无用功。

4、状态转移方程，其中的状态，初始值，这些都要考虑清楚。

对于模型，等我做过10道题目熟练之后再说吧，现在给出还为时过早。

题目：

首先明确状态，问问自己两个字符串对比有几种状态？下面用AB两个字符表示两个字符串

1、A的这个字母和B相同

2、A的这个字母和B不同，A和-对应

3、A的这个字母和B不同，B和-对应

最后出来的两个字符串一定是满足这个规则的。只有这三种状态。

那么状态转移方程呢？

1、明确目的，我们要求的是匹配的最后数字上面越大越好。

2、两个字母相同，那么是+5，其他都要减一个数，那么问题来了，这里千万不要以为相同就是最好的，如果这里认为相同就是最好的，那么你用的是贪心而不是dp了。

3、我们取之前的解为Y1，Y2，Y3，123对应上面三个状态,max（Y1+5，Y2-5，Y3-5）这里5是个虚数，可能是0也可能是负数。

4、要注意的有两点，第一，这个状态的之前那个状态的解，是不同的！如下面所示，如果我们处理第二个字符时候可能出现之前的情况就有下面三种

ATGC

GGGG

ATGC

-GGGG

-ATGC

GGGG

第二，Y1，Y2，Y3，是不同的，所以要取这三个值得max。

那么初始值呢？

初始值一般是二维数组的0行0列，这里要注意的是，这里的初始值不全是0，看看下面的情况

ATGC - - - -

- - - -GGGG

所以初始值应该是每一个字母都和空对应，而且要在之前那个值加上去，之前A和空对应如果是-3，那么T和空对应如果是-1，在二维数组中T这里的值应该是-4

最后输出二维数组中最右下角的值就是最后的解。

这里灵活之处是利用一个二维数组去保存了两个字母之间的关系，所以看起来代码特别清晰。

之后会对动态规划再细说的，这次就说这么多。