递归结构中的DP

1）表达式上的dp

问题：一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵，运算量为nmp。

矩阵乘法满足结合律，A*B*C可以表示成(A*B)*C或者是A*(B*C)，两者的运算量却不同。例如当A=2*3 B=3*4 C=4*5时，(A*B)*C=64而A*(B*C)=90。显然第一种顺序节省运算量。

现在给出N个矩阵，并输入N+1个数，第i个矩阵是a[i-1]*a[i]。

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=284

分析：跟区间dp一样，这个问题是在一个区间上进行动态规划的，假如我们要求 b-->e 区间上的最小值，我们找到一个中间区间 i ，让 b-->i 和 i -->e 的值最小，然后继续向下找

这是一个搜索的思想，可以用记忆话搜索降低复杂度。

其中的转移方程是 f【i】【j】 = f【i】【k】+f【k】【j】 + a [ i ] . x * a [ k ] . y * a [ j ] . y

如果不要求输出路径的话，可以用dp写，按照 j --  i 递增的顺序递推、

如果要求答应的路径的话，只能用记忆化搜索写，当然路径也是用递归写。

AC代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 15;
const int inf = 0x3f3f3f3f;

struct Node
{
    int x,y;
};
Node a[N];
int f[N][N],path[N][N];
int dp(int b,int e)
{
    if(b>=e)
        return 0;
    int& max=f[b][e];
    if(max!=0)
        return max;
    max=inf;
    for(int i=b; i<e; i++)
    {
        int tmp=dp(b,i)+dp(i+1,e)+a[b].x*a[i].y*a[e].y;  ///转移方程
        if(tmp<max)
        {
            max=tmp;
            path[b][e]=i;
        }
    }
    return max;
}
int print(int b,int e)
{
    if(b==e)
        printf("A%d",b);
    else
    {
        printf("(");
        print(b,path[b][e]);
        printf(" x ");
        print(path[b][e]+1,e);
        printf(")");
    }
}
int main()
{
    int n,cas=1;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1; i<=n; i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        memset(f,0,sizeof(f));
        memset(path,0,sizeof(path));
        printf("Case %d: ",cas++);
        dp(1,n);
        print(1,n);
        printf("\n");
    }
    return 0;
}
           

2）凸多边形上的dp