# 动态规划系列(1): 线性DP

## 从斐波那契数列说起

	// 使用递归计算斐波那契数列的第n项
int Fib(int n) {
if(n == 0)
return 0；
else if(n == 1)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}


#define MAX 1000
int f[MAX];

memset(f, -1, sizeof(f));
f[0] = 0; f[1] = 1;

int Fib(int n) {
if(f[n] != -1)
return f[n];
else
return (f[n] = Fib(n - 1) + Fib(n - 2));
}


#define MAX 1000
int f[MAX];

memset(f, -1, sizeof(f));
f[0] = 0; f[1] = 1;

int Fib(int n) {
for(int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];

return f[i];
}


## 初探状态设计：数塔 (HDU.2084)

### Sample Input

1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


### Sample Output

30


### 分析

1. 问题的开始条件（也即边界）在何处？
2. 问题的结束条件是什么？也即，何时我们停止一次搜寻，获得问题的一个解？
3. 我们怎样从问题的解空间中获取一个最优解？

### 题解

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 100;

int map[MAXN + 10][MAXN + 10];
int dp[MAXN + 10][MAXN + 10];

int main() {
ios::sync_with_stdio(false);

int c = 0;
cin >> c;

while(c--) {
int n = 0;
cin >> n;

for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> map[i][j];

memset(dp, 0, sizeof(dp));
dp[1][1] = map[1][1];

for(int i = 2; i <= n; i++)
for(int j = 1; j <= i; j++)
dp[i][j] = map[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1]);

int ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans, dp[n][i]);

cout << ans << endl;
}
}


## 状态设计进阶：最长公共子序列(HDU.1159)

### Problem Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, …, xm> another sequence Z = <z1, z2, …, zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, …, ik> of indices of X such that for all j = 1,2,…,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.  The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

### Sample Input

abcfbc abfcab
programming contest
abcd mnp


### Sample Output

4
2
0


### 题解

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1000;
char X[MAXN + 10], Z[MAXN + 10];
int f[MAXN + 10][MAXN + 10];

int main() {
while(scanf("%s %s", X + 1, Z + 1) != EOF) {
int n = (int)strlen(X + 1);
int m = (int)strlen(Z + 1);

memset(f, 0, sizeof(f));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(X[i] == Z[j]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}

printf("%d\n", f[n][m]);
}

return 0;
}


### 我们还能做些什么

#### 输出一个LCS的内容

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define UL 1
#define L 2
#define U 3

const int MAXN = 1000;

struct Node {
int status, arrow;
};

char X[MAXN + 10], Z[MAXN + 10];
Node f[MAXN + 10][MAXN + 10];

int LCSlength(char* X, char* Z, Node* f, int n, int m);
void PrintLCS(char* X, char* Z, Node* f, int p, int q);
int main() {
while(scanf("%s %s", X + 1, Z + 1) != EOF) {
int n = (int)strlen(X + 1);
int m = (int)strlen(Z + 1);

printf("%d\n", LCSlength(X, Z, f, n, m));
PrintLCS(X, Z, f, n, m);
putchar();
}

return 0;
}

int LCSlength(char* X, char* Z, Node* f, int n, int m) {
memset(f, 0, sizeof(f));

for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(X[i] == Z[j]) {
f[i][j].status = f[i - 1][j - 1] + 1;
f[i][j].arrow = UL;
} else {
if(f[i - 1][j].status > f[i][j - 1].status) {
f[i][j].status = f[i - 1][j].status;
f[i][j].arrow = U;
} else {
f[i][j].status = f[i][j - 1].status;
f[i][j].arrow = L;
}
}
}
}

return f[n][m].status;
}

void PrintLCS(char* X, char* Z, Node* f, int p, int q) {
if(p == 0 || q == 0)
return;

if(f[p][q].arrow == UL) {
PrintLCS(X, Z, f, p - 1, q - 1);
printf("%c ", X[p]);
} else if (f[p][q].arrow == U) {
PrintLCS(X, Z, f, p - 1, q);
} else {
PrintLCS(X, Z, f, p, q - 1);
}
}