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

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

### 分析

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

$f(i,j) = A(i,j)+max[f(i-1, j-1), f(i-1, j)]$

## 状态设计进阶：最长公共子序列(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.

### 分析

$f(i, j) = f(i-1, j-1) + 1$

$f(i,j)=max[f(i-1,j),f(i,j-1)]$

### 我们还能做些什么

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

$\begin{cases} & f(i,j)=f(i-1,j-1)+1,X[i]=Z[j]\\ & f(i,j)=max[f(i-1,j),f(i,j-1)],X[i] \neq Z[j] \end{cases}$

You need to set install_url to use ShareThis. Please set it in _config.yml.

### 评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.