递归结构中的DP

客官°小女子只卖身不卖艺 2022-08-26 12:20 92阅读 0赞

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][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

[http_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_284]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=284