算法设计与分析——动态规划——数字三角形问题

待我称王封你为后i 2022-11-16 08:32 190阅读 0赞

数字三角形问题  
1.题目描述：给定一个由n行数字组成的数字三角形，如图3-7所示。设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。  
算法设计:对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。  
![在这里插入图片描述][20210406203019520.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

#include<iostream>
    using namespace std;
    
    int Numeric_triangle(int **vector,int n,int **temp)
    {
        
    
    	
    		
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=1;j<=i;j++)
    		{
        
    			temp[i][j] = vector[i][j];
    		}
    		
    	}
    		
    	for(int i=n-1;i>=1;i--)//从倒数第二行开始往上递推
    	{
        
    		for(int j=1;j<=n;j++)
    		{
        
    			if(temp[i+1][j]>temp[i+1][j+1])//将每个数下面的两个数进行比较
    					temp[i][j]=temp[i][j]+temp[i+1][j]; //取较大的数加	
    
    			else
    					temp[i][j]=temp[i][j]+temp[i+1][j+1];
    		}
    	}
    	
    
    	return temp[1][1];
    	
    }
    
    int main()
    {
        
    	int n;
    	cout<<"输入数字三角形的高度";
    	cin>>n;
    	int **vector = new int *[n];
    	for(int i=1;i<=n;i++)
    	{
        
    		vector[i] = new int [n];
    	}
    	int **temp = new int *[n];
    	for(int i=1;i<=n;i++)
    	{
        
    		temp[i] = new int [n];
    	}
    
    	cout<<"输入数字三角形"<<endl;
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=1;j<=i;j++)
    		{
        
    			cin>>vector[i][j];
    		}
    	}
    	
    	cout<<"路径的最大和为："<<Numeric_triangle(vector,n,temp)<<endl;
    	
    	cout<<"自顶向下的路径为:";
    	cout<<"  "<<vector[1][1]<<" ";
    	int col=1;
    
    
    	for(int i=2;i<=n;i++)
    	{
        
    		if(temp[i][col]>temp[i][col+1])
    		{
        
    			cout<<vector[i][col]<<" ";
    		}	
    		else
    		{
        
    			cout<<vector[i][col+1]<<" ";
    			col++;
    		}
    	
    	}
    	
    		
    	return 0;
    	
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]

[20210406203019520.png]: /images/20221022/3c79a950353747fba10067ebb60eaa88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221022/0baaa5617fb247afb35e839c9e0633b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221022/21af83f723e742009ffb289fb0fd8abc.png