关于dp数塔类问题及其变形

悠悠 2022-09-20 11:12 186阅读 0赞

**数塔问题是一个很经典的问题，它是每个人学习动态规划的入门题，数塔问题也是理解和分析动态规划的经典，它里面所反映出现的性质也是相对于其他动态规划题目更明显，最优子结构和无后效性在数塔里面反映的很明显，如果一个数塔你是从后面往上计算的话，你从下面每一层往上计算的结果都是最优的，下一次你做出的决策是在上面最优的结果上面进行的。**

**做dp题目切记当前最优不一定是全局最优，比如最后一个例子中你如果只是记录两个脚的每次走的路径的话那么你只是做到当前最优，那么这样的话也一定是不对的，还有今天一个学长dp题目说道，做dp题目首先是列状态，怎么列状态呢，就是看看那些因素对结果产生了影响，比如位置、时间。。。**

**![9-7-1.jpg][]**

首先，经典是数塔问题大家都知道吧，从下往上dp每一步只能从下面的左边或者右边走过来选择一个最小的，最后dp到顶端也是就是最大的或者最小的一个值，当然从上往下dp也是可以的。对于当前的每一个点，也是只能从上边的左边或者右边选择一个最大的。最后在最后一行数中求一个最大值既为结果。

状态转移方程v\[i-1\]\[j\]+=v\[i\]\[j\]>v\[i\]\[j+1\]?v\[i\]\[j\]:v\[i\]\[j+1\];

## [The Triangle][] ##

从下往上求解代码：比较简单

#include <stdio.h>
    int v[100][100];
    int main()
    {
    	int n,i,j;
    	while(~scanf("%d",&n))
    	{
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<=i;j++)
    				scanf("%d",&v[i][j]);
    		}
    		for(i=n;--i;){
    			for(j=0;j<i;++j){
    				v[i-1][j]+=v[i][j]>v[i][j+1]?v[i][j]:v[i][j+1];
    			}
    		}
    		printf("%d\n",v[0][0]);
    	}
    	return 0;
    }

从上往下求解，比较复杂一点。

#include <iostream>
    using namespace std;
    intMax(int a,int b)
    {
        return a>b?a:b;
    }
    int main()
    {
        int a[110][110];
        int n;
        cin>>n;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=i; j++)
            {
                cin>>a[i][j];
            }
        }
        int max=0;
        for(int i=2; i<=n; i++)
        {
            for(int j=1; j<=i; j++)
            {
                a[i][j]+=Max(a[i-1][j-1],a[i-1][j]);
                if(a[i][j]>max)max=a[i][j];
            }
        }
        cout<<max<<endl;
        return 0;
    }

数塔是最简单的，也是最基础的，有很多题目都是其变形，一般不容易转化到数塔上，转化到数塔上面也是很简单。看一下nyoj上面这道。

## [免费馅饼][Link 1] ##

这个也是从上往下和从下往上都可以，这里只提供从下往上的代码，因为数塔类题目一般是从下往上求稍微比较容易一点，题意就不说了，思路就是一个数塔的思想，从下往上依次每次只能有三条路可以走，选择一个最短的路，跟数塔差别就是这个由三条路求最短的路，代码：

#include<stdio.h>
    #include<string.h>
    #define N 100010
    #define max(a,b,c)a>(b>c?b:c)?a:(b>c?b:c)
    int dp[N][13];//dp[i][j]表示 在第 i秒接住 j位置馅饼的情况下的最大接饼
    int main()
    {
        int i,j,t,x,n,maxt;
        while(scanf("%d",&n),n)
        {
            memset(dp,0,sizeof(int)*(n*13));
            for(i=1,maxt=-1; i<=n; i++)
            {
                scanf("%d%d",&x,&t);
                dp[t][x+1]++;//位置加 1， 便于后边计算
                maxt=maxt>t?maxt:t;
            }
            dp[0][6]=1;
            for(i=1; i<=maxt; i++)
            {
                for(j=1; j<=11; j++)
                {
                    int kk=max(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]);
                    if(kk!=0)
                        dp[i][j]+=kk;
                    else
                        dp[i][j]=0;
                }
            }
            int ans=-1;
            for(inti=1; i<=11; i++)
                if(ans<dp[maxt][i])
                    ans=dp[maxt][i];
            printf("%d\n",ans-1);
        }
        return
    }

继续变形，就是可以由n条路可以走了，这道题目：

# [威威猫系列故事——打地鼠][Link 2] #

这个题目从上到下和从下到上时一样的，每一层到下一层有n条路可以走，依次选择最小的路径依次dp即可。

代码：

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    int dp[25][505];
    int map[25][15];
    int main()
    {
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            for(int i=0; i<n; i++)
                for(int j=0; j<=500; j++)
                    dp[i][j]=9999999;
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<k; j++)
                    scanf("%d",&map[i][j]);
            }
            for(int j=0;j<k;j++)
            {
                dp[n-1][map[n-1][j]]=0;
            }
            for(int i=n-2; i>=0; i--)
            {
                for(int j=0; j<k; j++)
                {
                    for(int x=0; x<k; x++)
                    {
                        int tmp=dp[i+1][map[i+1][x]]+abs(map[i][j]-map[i+1][x]);
                        if(dp[i][map[i][j]]>tmp)
                            dp[i][map[i][j]]=tmp;
                    }
                }
            }
            int ans=9999999;
            for(int i=1; i<=500; i++)
            {
                //printf("%d ",dp[0][i]);
                if(ans>dp[0][i])
                    ans=dp[0][i];
            }
            printf("%d\n",ans);
        }
        return 0;
    }

上面的题目都是比较简单的，下面这个是数塔类变形的比较难得，难点在于转化

## [“炫舞家“ST][ST] ##

思路：dp\[i\]\[j\]\[k\]：表示第i次踩踏后两脚的位置j,k  
先固定一只脚的位置j,第i次踩踏后，状态为dp\[i\]\[j\]\[a\[i\]\]或者dp\[i\]\[a\[i\]\]\[j\],其中a\[i\]表示第i个输入的元素，则有状态方程：  
x=dp\[i-1\]\[k\]\[j\]+cost\[k\]\[a\[i\]\]; 是通过k踩过来的，cost\[k\]\[a\[i\]\]表示k->a\[i\]的花费。  
y=dp\[i-1\]\[j\]\[k\]+cost\[k\]\[a\[i\]\]; 是通过k踩过来的，cost\[k\]\[a\[i\]\]表示k->a\[i\]的花费。  
dp\[i\]\[j\]\[a\[i\]\]=dp\[i\]\[a\[i\]\]\[j\]=min(x,y)；  
答案：ans=min(dp\[n\]\[j\]\[a\[i\]\])

这道题目的难点在于用反面的思想去考虑。  
开始直接考虑用i和j两个值记录两个脚的位置，发现它两个脚那个脚移动到那个位置不止和前一个位置有关，就是不满足无后效性，后面看了一些别人的代码，看来dp还是学的不够熟练，其实这个题就是dp的思想，每一层两个脚从0---4 dp所有的情况，最后求到最后一步的最小的一个值既为答案。

看看代码：

#include <iostream>
    #include <math.h>
    using namespace std;
    const int def = 100000005;
    int a[10005],dp[10005][6][6];
    int cost[6][6]=
    {
        {1,2,2,2,2},
        {def,1,3,4,3},
        {def,3,1,3,4},
        {def,4,3,1,3},
        {def,3,4,3,1}
    };
    int main()
    {
        int i,j,k,ans,t,n,x,y;
        while(cin>>t&&t)
        {
            a[1]=t;
            for(n=2;; n++)
            {
                cin>>a[n];
                if(!a[n]) break;
            }
            for(i=0; i<=n; i++)
                for(j=0; j<5; j++)
                    for(k=0; k<5; k++)
                        dp[i][j][k]=def;
            dp[0][0][0]=0;
            ans=100000005;
            for(i=1; i<n; i++)
            {
                for(j=0; j<5; j++) //没动的脚
                {
                    if(j==a[i]) continue;
                    x=y=def;
                    for(k=0; k<5; k++) //左脚踩
                    {
                        if(k!=j||k+j==0) if(x>dp[i-1][k][j]+cost[k][a[i]]) x=dp[i-1][k][j]+cost[k][a[i]];
                    }
                    for(k=0; k<5; k++) //右脚踩
                    {
                        if(k!=j||k+j==0) if(y>dp[i-1][j][k]+cost[k][a[i]]) y=dp[i-1][j][k]+cost[k][a[i]];
                    }
                    if(x>y) x=y;
                    dp[i][j][a[i]]=dp[i][a[i]][j]=x;
                    if(ans>dp[n-1][j][a[i]]) ans=dp[n-1][j][a[i]];
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

没时间了。有时间详细解释一下。总结到这里。

[9-7-1.jpg]: http://www.qzyz.cn/oi/jc/9-7-1.jpg
[The Triangle]: http://acm.nyist.net/JudgeOnline/problem.php?pid=18
[Link 1]: http://acm.nyist.net/JudgeOnline/problem.php?pid=613
[Link 2]: http://acm.hdu.edu.cn/showproblem.php?pid=4540
[ST]: http://acm.nyist.net/JudgeOnline/problem.php?pid=740