動(dòng)態(tài)規(guī)劃作為暑期集訓(xùn)第一天的內(nèi)容，相對(duì)簡(jiǎn)單一些，然而動(dòng)態(tài)規(guī)劃后面也有幾道很難的題目，我們以第一道數(shù)字三角形開始：
題目：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]等于，第二層兩個(gè)元素到最底層的M[2][1]和M[2][2]中最大值與第一層元素的和；第二層的某個(gè)元素的到最底層的M[i][j]等于這個(gè)元素下面兩個(gè)元素的M[i+1][j]和M[i+1][j+1]中大的一個(gè)和該元素的和。
用數(shù)學(xué)符號(hào)表示出來就是：
?????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;
}
我們?cè)诮鉀Q動(dòng)態(tài)規(guī)劃問題時(shí)，要注意的就是：
- 問題具有最優(yōu)子結(jié)構(gòu)性質(zhì):如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
- 無后效性:當(dāng)前的若干個(gè)狀態(tài)值一旦確定，則此后過程 的演變就只和這若干個(gè)狀態(tài)的值有關(guān)，和之前是采取哪 種手段或經(jīng)過哪條路徑演變到當(dāng)前的這若干個(gè)狀態(tài)，沒有關(guān)系。
我們來看第二道題：
問題描述:
??一個(gè)數(shù)的序列ai，當(dāng)a1 < a2 < ... < aS的時(shí)候，我們稱這個(gè)序列是上升的。對(duì)于給定的一個(gè)序列(a1, a2, ..., aN)，我們可以得到一些上升的子序列(ai1, ai2, ..., aiK)，這里1 <= i1 <i2 < ... < iK <= N。比如，對(duì)于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長(zhǎng)的長(zhǎng)度是4，比如子序列(1, 3, 5, 8).
??這是一個(gè)一維的動(dòng)態(tài)規(guī)劃問題，對(duì)比起來比上一個(gè)問題還要簡(jiǎn)單，我們用maxLen(k)表示以$a_{k}$做為“終點(diǎn)”的最長(zhǎng)上升子序列的長(zhǎng)度，那么我們有
??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]);//出錯(cuò)了一次！把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;
}
再看一道，二維的問題最長(zhǎng)公共子序列
??給出兩個(gè)字符串，求出這樣的一個(gè)最長(zhǎng)的公共子序列的長(zhǎng)度:子序列中的每個(gè)字符都能在兩個(gè)原串中找到，而且每個(gè)字符的先后順序和原串中的先后順序一致。
example:
abcfbc abfcab //最大子串為abcb, 所以結(jié)果為4
programming contest //最大子串為on，所以結(jié)果為2
解題思路：
??我們記：M[i][j]是第一個(gè)和第二個(gè)字符串前i和前j個(gè)元素組成的字串，公共子串的長(zhǎng)度，那么：
- 如果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;
}
今天就先介紹一二維的動(dòng)態(tài)規(guī)劃問題。
