动态规划作为暑期集训第一天的内容，相对简单一些，然而动态规划后面也有几道很难的题目，我们以第一道数字三角形开始：
题目：The Triangle
描述：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
首先，将我们要求得的max值记成M[i][j]
我们将问题分解成子问题：
即最高层到最底层的M[1][1]等于，第二层两个元素到最底层的M[2][1]和M[2][2]中最大值与第一层元素的和；第二层的某个元素的到最底层的M[i][j]等于这个元素下面两个元素的M[i+1][j]和M[i+1][j+1]中大的一个和该元素的和。
用数学符号表示出来就是：
MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)}
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t;
cin>>t;
int D[t][t];
memset(D, 0, sizeof(D));
for (int i = 0; i < t; i++) {
for (int j = 0; j <= i; j++) {
cin>>D[i][j];
}
}
int x, y;
for (int i = t - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
x = D[i + 1][j];
y = D[i + 1][j + 1];
D[i][j] = max(x, y) + D[i][j];
}
}
cout<<D[0][0];//*/
return0;
}
我们在解决动态规划问题时，要注意的就是：
- 问题具有最优子结构性质:如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
- 无后效性:当前的若干个状态值一旦确定，则此后过程 的演变就只和这若干个状态的值有关，和之前是采取哪 种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
我们来看第二道题：
问题描述:
一个数的序列ai，当a1 < a2 < ... < aS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 <i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).
这是一个一维的动态规划问题，对比起来比上一个问题还要简单，我们用maxLen(k)表示以$a_{k}$做为“终点”的最长上升子序列的长度，那么我们有
maxLen (k) = max { maxLen (i):1<=i < k 且 $a_{i}$< $a_{k}$且 k≠1 } + 1(如果找不到这样的i，就让其等于一)
#include <iostream>
#include <algorithm>
#include <string.h>
#define maxn 1001
usingnamespacestd;
int MaxSubSequenceLength(int D[], int t) {
int l;
int len[t];
//memset(len, 0, sizeof(len)); //不能通过这样全部初始化为1!
for (int i = 0; i < t; i++) {
len[i] = 1;
}
for (int i = 1; i < t; i++) {
for (int j = 0; j < i; j++) {
if (D[i] > D[j]) {
len[i] = max(len[j] + 1, len[i]);//出错了一次！把1写在了外面
}
}
}
l = *max_element(len, len + t);
cout<<l;
return0;
}
int main(int argc, constchar * argv[]) {
int t;
cin>>t;
int D[t];
for (int i = 0; i < t; i++) {
cin>>D[i];
}
MaxSubSequenceLength(D, t);
return0;
}
再看一道，二维的问题最长公共子序列
给出两个字符串，求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。
example:
abcfbc abfcab //最大子串为abcb, 所以结果为4
programming contest //最大子串为on，所以结果为2
解题思路：
我们记：M[i][j]是第一个和第二个字符串前i和前j个元素组成的字串，公共子串的长度，那么：
- 如果A_{i}=B_{j}，那么M[i][j] = M[i - 1][j - 1] + 1
- 否则，M[i][j] = max(M[i][j - 1], M[i - 1][j])
#include <iostream>
#include <string.h>
#include <algorithm>
usingnamespacestd;
int main() {
string A,B;
while (cin>>A>>B) {
int a = A.size();
int b = B.size();
int D[a + 1][b + 1];
memset(D, 0, sizeof(D));
for (int i = 0; i <= a; i++) {
D[i][0] = 0;
}
for (int i = 0; i <= b; i++) {
D[0][i] = 0;
}
for (int i = 1; i <=a; i++) {
for (int j = 1; j <= b; j++) {
if (A[i - 1] == B[j - 1]) {
D[i][j] = D[i - 1][j - 1] + 1;
} else {
D[i][j] = max(D[i - 1][j], D[i][j - 1]);
}
}
}
cout<<D[a][b]<<endl;
}
return0;
}
今天就先介绍一二维的动态规划问题。
