动态规划小结

一 简介

当遇到最优值问题时，往往采用的是动态规划算法，而采用动态规划计算获取的最优解是通过无数而且重复的子问题时，就非常有效。根据算法导论上的讲解，顺序如下:

1.分析最优解的结构

2.定义出解的递归表达式

3.进行自底向上的求值

4.从子问题中构造一个最优解

其中定义出 一个好的递归定义式是关键，递归式分析以下几种：

1.如果找出第i项与第i-1项之间的关系/理想情况

2.如果找出第i项与第k项之间的关系/一般情况

另外，在进行自底向上的求解过程中，采用的循环起始点需要进行考究，以满足自底向上的特征，递归式一般形式为:

1.s[i] = min/max{s[k] + f(k)};起始条件

2.s[i,j] = min/max{s[i,k]+s[k+1,j]};子问题的起始循环条件

其中f[k]为代价函数，这里面的s[i,j],d[i]：一般情况下为前面i项的和形式，这样才能更好的列出递归公式。

二 例题

求数组最长递增子序列

最为普通的方法就是采用递归式2，递归式如下:

其中l[i,k]:从i到k的递增序列最小值，m[k+1,j]:从k+1到j的递增序列中最大值

上面的式子都需要更新两个数组:l[i,j] = l[i,k],m[i,j] = m[k+1,j]

相应的代码如下:

void increase1(int a[],int size)
{
int s[size][size],i,j,k;
int m[size][size],l[size][size];

//m[i][j]:i到j中递增记录中的最后一个元素
//l[i][j]:i到j中递增记录中的第一个元素
//s[i][j]:i到j中的递增记录的长度
for(i=0;i
{
for(j=0;j
{
m[i][j] = a[j];
l[i][j] = a[j];
s[i][j] = 1;
}
s[i][i] = 1;
m[i][i] = a[i];
l[i][i] = a[i];

if((i+1)

s[i][i+1] = 2;
m[i][i+1] = a[i+1];
l[i][i+1] = a[i];
}
}

for(i=size-3;i>=0;i--)
for(j=i+2;j
for(k=i;k
{
if(s[i][j] < (s[i][k] + s[k+1][j]) && m[i][k] < l[k+1][j])
{
s[i][j] = s[i][k]+s[k+1][j];
l[i][j] = l[i][k];
m[i][j] = m[k+1][j];
}
else if(s[i][j] == (s[i][k] + s[k+1][j]) && m[k+1][j]
{
m[i][j] = m[k+1][j];
s[i][j] = s[i][k] + s[k+1][j];
l[i][j] = l[i][k];
}

printf("i:%d,j:%d,k:%d,s[%d][%d]:%d,s[%d][%d]:%d,s[%d][%d]:%d,\
m[%d][%d]:%d,l[%d][%d]:%d\n",i,j,k,i,j,s[i][j],i,k,s[i][k],k+1,j,s[k+1][j],i,j,m[i][j],i,j,l[i][j]);
}

for(i=0;i
for(j=0;j
printf("m[%d][%d]:%d,l[%d][%d]:%d\n",i,j,m[i][j],i,j,l[i][j]);

printf("0-->%d:%d\n",size-1,s[0][size-1]);
}

为了降低复杂度，就需要采用递归式2,采用直接套用上面的方法列出递归式2如下：

与之对应的程序如下:

//s[j] = max{1+s[i]} 0<i<j s[i]:以元素i为尾的长度
void increase2(int a[],int size)
{
    int s[size],i,j;
    int max;

    for(i=0;i<size;i++)    s[i] = 1;

    max = INT_MIN;

    for(i=0;i<size;i++)
     for(j=i+1;j<size;j++)
    {
      if(a[i]<=a[j] && s[j]<(1+s[i]))
      {
        s[j] = 1+s[i];
        max = max < s[j]?s[j]:max;
      }
      printf("i:%d,s[%d]:%d\n",i,j,s[j]);
    }

    printf("max:%d\n",max);
}

现在仍然需要想办法来降低复杂度，通过分析程序发现，第二重循环为一查找过程，通过查找递增，并且长度大的序列，不妨将其事先进行保存在一个有序序列中，这样就会降低复杂度，即下面的程序:

int increase3(int a[],int size)
{
int i,j,k,mid;
//l[i]:记录长度为i+1的最后一个元素
//d[i]:结尾为a[i]的递增序列长度
int l[size],d[size];

for(i=0;i
{
d[i] = 1;
l[i] = 0;
}

d[0] = 1;
l[0] = a[0];
j = 0;
for(i=1;i
{
//从0~j查找满足条件的最后一个元素
k = 0;
while(k
{
mid = (k+j)/2;
if(a[i]
else		k = mid+1;
}
printf("before k:%d,j:%d,l[%d]:%d,d[%d]:%d,a[%d]:%d\n",\
k,j,k,l[k],i,d[i],i,a[i]);
if(l[k] < a[i]) {
d[i] = k+1;
if(l[k+1]==0 ||l[k+1]>a[i])
l[k+1] = a[i];
j = k+1;
}
else {
l[k] = a[i];
j = k;
}
printf(" after k:%d,j:%d,l[%d]:%d,d[%d]:%d,a[%d]:%d\n",\
k,j,k,l[k],i,d[i],i,a[i]);
}
//	for(i=0;i
//	printf("increase3 l[%d]:%d\n",i,l[i]);
printf("max:%d\n",j+1);
}

参考资料:

1.算法导论

2.编程之美

3.一些网上LaTex资料