BearKing


私信TA

用户名:Bearking

访问量:12204

签 名:

天道酬勤

等  级
排  名 581
经  验 4067
参赛次数 0
文章发表 20
年  龄 0
在职情况 学生
学  校 XXXY
专  业 大数据

  自我简介:

不要轻易放弃自己的梦想,总有一点天,它会在你手中发光!

题目简述(题目:2127' https://www.dotcpp.com/oj/problem2127.html  '):


        数字三角形如下: 

                 7

                3 8

               8 1 0

              2 7 4 4

             4 5 2 6 5

        在上面的数字三角形中寻找一条从顶部到底部的路径,使得路径上所经过的数字之和

最大。路径上的每一步都只能往左下或者右下走。

三角形的行数大于1小于等于100,数字为0-99.


我们先考虑怎么存:

        很容易就想到用二维数组a[N][N]来存储,样例输入:

         5
        13
        11   8
        12   7   26
         6   14  15   8
        12   7   13  24 11

//输入功能
void input(int a[N][N],int n)
{
	int i,j;
	for(i=1;ia[i][j];
}


思路探讨:

        从下往上走,将倒数第二行相邻的最后一行元素中的最大值与自身相加,

并替换当前元素,循环此操作,一直到最顶端为止,输出最顶端元素的值就是所得的最大值

我们从下往上推出来的动态转移方程公式:max = a[i+1][j]>=a[i+1][j+1] ? a[i+1][j] : a[i+1][j+1];

我们从小往上递推一下


图解思想:

无标题.png 

经上面的图解探讨,可以看出从下往上选最大并更新上一层,以此类推,最后一张图就是只剩下最后所要结果:86

这样可以用递推思想去设计更直观些



我们要用递归写的话,直接从上往下推,更适合递推算法的一层一层深入的模式,一直深入到最底层在按上面图解方式一层一层回溯上来!

递归:


我们用MaxSum(r, j)表示从a(r,j)到底边的各条路径中,最佳路径的数字之和。
因此,此题的最终问题就变成了求 MaxSum(1,1)
当我们看到这个题目的时候,首先想到的就是可以用简单的递归来解题:
a(r, j)出发,下一步只能走a(r+1,j)或者a(r+1, j+1)。故对于N行的三角形,我们可以写出如下的递归式:

if ( r == N)                
    MaxSum(r,j) = a(r,j)  
else      
    MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + a(r,j)

上面一番讨论借用上面简单的递归思想直接实现:

#include   
#include  
#define MAX 500
using namespace std; 
int a[MAX][MAX];  
int n;  
int MaxSum(int i, int j){    
    if(i==n)  
        return a[i][j];    
    int x = MaxSum(i+1,j);    
    int y = MaxSum(i+1,j+1);    
    return max(x,y)+a[i][j];  
}
int main(){    
    int i,j;    
    cin >> n;    
    for(i=1;i a[i][j];    
    cout << MaxSum(1,1) << endl;  
}

上面的代码很暴力,当中有大量重复计算O(2^n) 


因此我们用DP来优化,使之成为记忆递归型的动态规划程序

#include   
#include  
using namespace std;

#define MAX 500

int a[MAX][MAX];    
int n;  
int maxSum[MAX][MAX];

int MaxSum(int i, int j){      
    if( maxSum[i][j] != -1 )         
        return maxSum[i][j];      
    if(i==n)   
        maxSum[i][j] = a[i][j];     
    else{    
        int x = MaxSum(i+1,j);       
        int y = MaxSum(i+1,j+1);       
        maxSum[i][j] = max(x,y)+ a[i][j];     
    }     
    return maxSum[i][j]; 
} 
int main(){    
    int i,j;    
    cin >> n;    
    for(i=1;i a[i][j];       
            maxSum[i][j] = -1;   
        }    
    cout << MaxSum(1,1) << endl; 
}



从下往上推,往下方便我们优化空间

递推:

虽然在短时间内就AC了。但是,我们并不能满足于这样的代码,因为递归总是需要使用大量堆栈上的空间,很容易造成栈溢出,我们现在就要考虑如何把递归转换为递推,让我们一步一步来完成这个过程。

根据动态转移方程,我们用一个C函数来概括出递推的过程:

//循环倒叙往上加
void cancle(int a[N][N],int n)
{
	int i,j,max=0;
	for(i=n-1;i>=1;i--)
		for(j=1;j=a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
			//更新当前元素的值
			a[i][j]=a[i][j]+max;	 //让其自己和自己下方相邻元素的最大值相加
		}
	printf("%d",a[0][0]);                    //C++:cout<<a[0][0];
}


我们添加一项来探讨:

当我不仅仅要最大值,而且还要打印出从下往上累加的路线,那我们该怎么办??

很简单,用多维数组来存储该过程:a[3][N][N]

C代码详解:

#includeint main01()
{
	int n,a[3][500][500],i,j;
	//printf("请输入数塔的层数:");
	scanf("%d",&n);
	//printf("请输入数塔:\n");
	getchar();
	for(i=1;i<=n;i++)
		for(j=1;j=1;i--)
		for(j=1;ja[2][i+1][j+1])
			{
				a[2][i][j]=a[2][i][j]+a[2][i+1][j];
				a[0][i][j]=0; 
			}
			else
			{
				a[2][i][j]=a[2][i][j]+a[2][i+1][j+1];
				a[0][i][j]=1;
			}
			printf("%d\n",a[2][1][1]);
			for(i=1,j=1;i<n;i++)
			{
				printf("%d->",a[1][i][j]);
				j=j+a[0][i][j];
			}
			printf("%d\n",a[1][n][j]);
	return 0;
}

运行结果图:

QQ截图20201023163751.png


注意:

虽然我们通过上面的步骤一步一步的走过来,但是,当我们再深入探讨的时候,就有发现问题了,如果我们存入的数塔非常大,那么我们开辟的内存空间也会非常大,这样就会导致大量的空间资源浪费,所以我们可以借助滚动数组来优化算法(我博客中"背包问题"也提到过:' https://blog.dotcpp.com/a/73345  ',可以通过多种不同类型题来提高该方面的理解)


在改变之前,我们需要先改进思路,用两个二维数组来实现:

#include#includeusing namespace std;
/* 
int main()
{
	int i,j,D[500][500],maxsum[500][500],n;
	for(i = 0;i < n;i ++)
		for(j = 0;j < n;j ++)
			cin>>a[i][j];
	//把a数组最后一行放入b数组 
	for(i = 0;i < n;i ++)
		maxsum[i][j] = a[i][j];
	//从下往上递推
	for(i = n - 2;i >= 0;i --)
		for(j = 0;j <= i;j ++)
			maxsum[i][j] = max(maxsum[i+1][j],maxsum[i+1][j+1]) + D[i][j];
	//打印顶端
	cout<<maxsum[0][0]<<endl;
	return 0;
}
*/


回到思想探讨上:

        我们可以在创建一个一位数组,用一位数组从下往上在保存数据的二维数组上执行,每执行一行数组往上挪动,滚动到最后直接打印一维数组第一个元素即可!


C代码演示:

#include#includeusing namespace std;

/*空间优化
	没必要用二维数组存储每一个相对大的元素(maxa[][]),只要从底层一行行向上递推,
那么只要一维数组(maxa[])即可,即只要存储一行maxa[]值就可以。 

空间再优化
	不要maxsum一维数组也不要了,一直用D的第n行,达到空间优化。
*/ 
int main()
{
	//用一个maxsum指针来代替数组功能 
	int i,j,a[500][500],*maxsum,n;
	cin>>n;
	for(i = 1;i a[i][j];
	//让maxsum指向第n行 
	maxsum = a[n];
	//从下往上递推
	for(i = n - 1;i >= 1;i --)
		for(j = 1;j <= i;j ++)
			maxsum[j] = max(maxsum[j],maxsum[j+1]) + a[i][j];
	//打印顶端
	cout<<maxsum[1];
	return 0;
}



数塔问题的整个探讨过程是很有价值的,尤其是对于刚接触动态规划问题的人,需要多深究这些经典问题!

在精不在多!

 

0.0分

14 人评分

  评论区

非常有用的文章,谢谢分享
2020-10-28 11:13:12
  • «
  • 1
  • »