动态规划：样例讲解一篇通

概念讲解

动态规划是把大问题分解成子问题（但不能简单的分解，子问题要具有相同子结构的解），并综合子问题的解，导出大问题的解，问题求解耗时会按问题规模呈幂级数增加。

基本方法：为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中。

举例

【问题】 求两字符序列的最长公共字符子序列
假设，两个 序列 a[],b[]，有公共最长子序列 z[]
则必须具有如下性质：
    （1）a和b两序列尾末元素相等（a[m] == b [n]）时，则同时去除尾部元素后，新的公共子序列为z去除尾部元素（“z[0]...z[k-1]”为a[m-1]和b [n-1]两序列的公共子序列）。
    （2）而a和b两序列尾部元素不相等(a[m] != b [n])时，
    若z[k]!=a[m]，则“z[0]...z[k-1]”为a[m-2]和b[n-1]两序列的公共子序列
    若z[k]!=b[m]，则“z[0]...z[k-1]”为a[m-1]和b[n-2]两序列的公共子序列

由以上性质可以划分子问题，
    找ab的公共子序列，
        若a[m] == b [n]则进一步解决子问题 a[m-1]和b[n-1]的公共子序列。
        若不相等则子问题为找出（a[m-2]和b[n-1]）的公共子序列L1，再找出（a[m-1]h和b[n-2]）的公共子序列L2，取L1和L2中较长的作为最长公共子序列，也就是哪个长用哪个。

程序设计

    引进两个辅助数组（用于构造最优解）
    用c[i][j]记录a[i]与b[j]的LCS 的长度
    用d[i][j]记录c[i][j]是通过哪个子问题取得的（-1,0,1标识左、左上、上三个方向）
伪代码
    a和b的序列长度分别是m,n
    如a[m] == b[n]，则公共子序列长度c[m,n] = c[m - 1, n -1] + 1；（i--，j--）
    如a[m] != b[n]，则c[m,n] = max{c[m,n - 1], c[m - 1, n]}; ( c[i,j-1]>=c[i-1,j]时则j--，否则i--；)
    其中，i和j作为index，分别从m,n开始，递减循环直到i = 0，j = 0

声明： 以下内容，引自网络

执行代码

#include <stdio.h>
#include <string.h>
#define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
    int i, j;

    for(i = 0; i <= m; i++)
        c[i][0] = 0;
    for(j = 1; j <= n; j++)
        c[0][j] = 0;
    for(i = 1; i<= m; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 0;
            }
            else if(c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 1;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = -1;
            }
        }
    }
}

void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
    if(i == 0 || j == 0)
        return;
    if(b[i][j] == 0)
    {
        PrintLCS(b, x, i-1, j-1);
        printf("%c ", x[i-1]);
    }
    else if(b[i][j] == 1)
        PrintLCS(b, x, i-1, j);
    else
        PrintLCS(b, x, i, j-1);
}

int main(int argc, char **argv)
{
    char x[MAXLEN] = {"ABCBDAB"};
    char y[MAXLEN] = {"BDCABA"};
    int b[MAXLEN][MAXLEN];
    int c[MAXLEN][MAXLEN];
    int m, n;

    m = strlen(x);
    n = strlen(y);

    LCSLength(x, y, m, n, c, b);
    PrintLCS(b, x, m, n);

    return 0;
}