一、步骤
1、刻画最优解的结构特征；
2、递归的定义最优解的值；
3、计算最优解的值，通常采用自底向上的方法；
4、利用计算出的信息构造一个最优解。
二、例子（最长公共子序列问题）
问题描述：
给定两个字符串A[m]、B[n]，求它们的最长公共子序列C。
1、刻画最优解的结构特征
如果temp=A[m]=B[n]，C=temp+max_common_len(A[1,...,m-1],B[1,...,n-1])；
如果A[m]!=B[n]，则C=maxLen(max_common_len(A[1,...,m],B[1,...,n-1])，max_common_len(A[1,...,m-1],B[1,...n]))。
2、递归的定义最优解的值
设C[i,j]表示两个串A[i]与B[j]的最长公共子序列的长度，则
if i=j=0, C[i,j]=0;
if i,j>0 and A[i]==B[j], C[i,j]=1+C[i-1,j-1];
if i,j>0 and A[i]!=B[j], C[i,j]=max(C[i-1,j],C[i,j-1]).
3、计算最优解
LCS
原文：http://www.cnblogs.com/luori719/p/5237950.html