算法学习(二)：动态规划（DP）（1）

一：基本思想
与分治法类似，其基本思想也是将待求问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，DP求解的问题，经分解得到的子问题往往不是互相独立的。
二：解题步骤
1）：分析一个最优解决方案应该具备的结构
2）：递归定义最优解决方案
3）：由底至上构建一个最优解决方案
三：经典题目
1：最长公共子序列LCS：已知两个数列S1和S2，长度分别为m和n，求最长公共子序列的长度和序列
设c[i,j]=LCS{S1[1…i],S2[1…j]}，则c[m,n]=LCS{S1,S2},注意到
{c[i-1,n-1]+1 S1[i]=S2[j]
c[i,j]={max{c[i-1,j],c[i,j-1]} S1[i]≠S2[j]
这便是此问题的最优子结构特性，代码如下：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
char A[100];
char B[100];
char S[100];//用来记录最长公共子序列
int c[100][100]={0};//用来记录当前最长公共子序列长度
void readdata()
{
    cin>>A;
    cin>>B;
}
int lcs()
{
    int m = strlen(A);
    int n = strlen(B);
    int k=0;
    for(int i = 1;i <= m;i++)//从1开始，防止出现数组角标为-1
        for(int j = 1;j <= n;j++)//从1开始
    {
        if(A[i-1]==B[j-1])//字符串本身是从0开始
            {
                c[i][j]=c[i-1][j-1]+1;
                if(i>=j)//保证顺序正确
                    S[k++]=A[i-1];//记录公共数据
            }
        else if(c[i-1][j]>c[i][j-1])
            c[i][j]=c[i-1][j];
        else
            c[i][j]=c[i][j-1];
    }
    return c[m][n];//返回最长公共子序列
}
int main()
{
    readdata();
    cout<<lcs()<<endl;
    cout<<S<<endl;
    return 0;
}