精华内容
下载资源
问答
  • 数字三角形问题 动态规划 OJ 问题:Triangle(参见 http://poj.org/problem?id=1163) 题意:在数字三角形上寻找一条沿相邻顶点从顶到底走的路径,使路径上的数字和最大。 输入:三角形高度 n,数字三角形数值。 ...

    数字三角形问题 动态规划

    OJ 问题:Triangle(参见 http://poj.org/problem?id=1163)
    题意:在数字三角形上寻找一条沿相邻顶点从顶到底走的路径,使路径上的数字和最大。
    输入:三角形高度 n,数字三角形数值。
    输出:最大数字和。

    在这里插入图片描述

    解决思路:

    由下而上逐个计算个点到最低端的最大路径,因为最大路径的子路径也一定是最大路径,而且右下而上只有两个方向,一个是正上方一个是右上方
    比如4到达最顶端的最大路径的子路径一定包含2和7,而2到顶端的最大路径一定包含8或者1,以此类推
    我们用一个数组表示范围一个数组表示距离
    在这里插入图片描述

    解题代码

    #include<iostream>
    using namespace std;
    
    int main(){
    	//输入的数组
    	int arr[100][100];
    	//表示距离的数组
    	int max[100][100]={0};
    	//输入三角形的行数
    	int length;
    	cin>>length;
       //逐个输入元素
       for(int i=1;i<=length;i++){
       	for(int j=1;j<=i;j++){
       		cin>>arr[i][j];
       		if(i==length){
       			//最底层的最大路径是本身 
    		   max[i][j]=arr[i][j]; 
    	   }
       } 
       } 
       //从底层开始递推
      for(int j=length-1;j>=1;j--){
      	for(int i=1;i<=length-1;i++){
      		//正下方 
      		int one=max[j+1][i];
      		int two=max[j+1][i+1];
    		if(one>=two){
    			max[j][i]=one+arr[j][i]; 
    		 } else{
    		 	max[j][i]=two+arr[j][i] ; 
    		  } 
    	  } 
      } 
      cout<<max[1][1]<<endl;
       
    } 
    

    在这里插入图片描述

    以上就是数字三角形问题 动态规划的解决方案,如有帮助还请点赞关注支持,如有疑问评论私信都可,看到后可帮助解答本博客主要侧重于数据结构于算法和java开发,操作系统,计算机网络,觉得我的文章有帮助的小伙伴可以关注我,有疑问可评论私信,相逢即是缘,大家高处见

    在这里插入图片描述

    展开全文
  • Problem Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从三角形的顶至...

    Problem Description

    给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。

    对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值。

    Input

    输入数据的第1行是数字三角形的行数n,1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0…99之间。

    Output

    输出数据只有一个整数,表示计算出的最大值。

    Sample Input

    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

    Sample Output

    30

    #include<iostream>
    #include<math.h>
    #include<cstring>
    using namespace std;
    int main()
    {
    	int a[110][110],i,j,n,k,l,p[110];
    	cin>>n;
    	memset(p,0,sizeof(p));
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<=i;j++)
    		{
    			cin>>a[i][j];
    		} 
    	}
    	for(j=n-1;j>=0;j--)
    	{		
    		for(i=0;i<=j;i++)
    		{
    			p[i]=a[j][i]+max(p[i],p[i+1]);
    		}
    	}
    	cout<<p[0];
    	return 0;
     }
    
    
    展开全文
  • Problem Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从三角形的顶...

    Problem Description

    给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。
      
    对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值。

    Input

    输入数据的第1行是数字三角形的行数n,1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

    Output

    输出数据只有一个整数,表示计算出的最大值。

    Sample Input

    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

    Sample Output

    30

    code:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int a[110][110], b[110][110];
        int n;
        scanf("%d", &n);
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<=i;j++)
            {
                scanf("%d", &a[i][j]);
            }
        }
    
        for(int i = 0;i<n;i++)
        {
            b[n-1][i] = a[n-1][i];
        }
    
        for(int i = n-2;i>=0;i--)
        {
            for(int j = 0;j<=i;j++)
            {
                b[i][j] = max(b[i+1][j]+a[i][j], b[i+1][j+1]+a[i][j]);
            }
        }
    
        printf("%d\n", b[0][0]);
    }
    

     

    展开全文
  • 动态规划——数字三角形问题 OJ问题:Triangle(参见http://poj.org/problem?id=1163) 题意:在数字三角形上寻找一条从顶到底的路径,使路径上的数字和最大。 实验方法1: 动态规划。设立二维数组d[n][n],d[i][j]...

    动态规划——数字三角形问题

    OJ问题:Triangle(参见http://poj.org/problem?id=1163)
    题意:在数字三角形上寻找一条从顶到底的路径,使路径上的数字和最大。
    在这里插入图片描述

    实验方法1:

    动态规划。设立二维数组d[n][n],d[i][j]表示a[1][1]至a[i][j]的最大路径和,或者表示在以a[i][j]为顶的子三角形中的最大路径和。

    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int n,a[100][100],d[100][100];
    	cin>>n;
    	for(int i=0;i<n;i++){
    		for(int j=0;j<i+1;j++){
    			cin>>a[i][j];
    		}
    	}
    	for(int i=n-1;i>=0;i--){
    		for(int j=0;j<=i;j++){
    			if(i==n-1){
    				d[i][j]=a[i][j];
    			}
    			else{
    				d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);
    			}
    		}
    	}
    	cout<<d[0][0]<<endl;
    	return 0;
    } 
    

    实验方法2:

    备忘录方法。设立二维数组d[n][n]。设计递归函数int memoir(int i, int j),主函数调用memoir (n,n),然后得到所求最大和。

    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int n,a[100][100],d[100][100];
    int memoir(int i,int j)
    {
    	if(d[i][j]!=0){
    		return d[i][j];
    	}
    	else{
    		if(i==n-1){
    			return a[i][j];
    		}
    		else{
    			d[i][j]=a[i][j]+max(memoir(i+1,j),memoir(i+1,j+1));
    			return d[i][j];
    		}
    	}
    }
    int main()
    {
    	cin>>n;
    	for(int i=0;i<n;i++){
    		for(int j=0;j<i+1;j++){
    			cin>>a[i][j];
    		}
    	}
    	memset(d,0,sizeof(d));
    	memoir(0,0);
    	cout<<d[0][0]<<endl;
    	return 0;
    }
    
    展开全文
  • 有如下一个数字三角形: 73 88 1 02 7 4 44 5 2 6 5 从定点出发,在每个节点可以选择向下走或者向右下走,一直走到底层。试设计一种算法,计算从三角形顶端到底部的一条路径,是该路径...
  • 这是动态规划很经典的一个问题 就是一个三角形类似这样:  2 3 4 输出顶点的到底部的最大和,限制条件元素只能左下或者右下走 例如:上述这个三角形,这个输出就是6 解决方法:动态规划 定义的dp数组的小只需要和...
  • 数字三角形问题 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径...
  • C++写的,利用动态规划解决数字三角形问题,含.cpp文件一个。
  • 动态规划之数字三角形问题

    千次阅读 2020-08-05 17:01:35
    问题描述 在数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或者右下走。只需要求出这个最大和即可。不必给出具体路径。 三角形的行数大于1小于等于100,数字...
  • 数字三角形问题 Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从...
  • 动态规划实现数字三角形问题  (1)题目描述如图所示      (2)我们用上述矩阵分析:自顶向下分析入下图二维矩阵所示  (3)我们从arr[2][0]开始分析,arr[2][0]是计算当前位置按照题中...
  • 利用动态规划思想求解数字三角形问题
  • 先看几类数字三角形的问题,通过对这几个问题的分析来理解有关动态规划的基本思想 数字三角形I 问题描述:  有一个由正整数组成的三角形,第一行只有一个数,除了最下行之外 每个数的左下方和右下方各有一个数,...
  • 数字三角形问题 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大...
  • 动态规划-数字三角形问题

    万次阅读 多人点赞 2018-11-04 19:23:44
    如果熟悉回溯法,可能会立刻发现这是一个动态的决策问题:每次有两种选择-左下或右下。如果用回溯法求出所有可能的路线,就可以从中选出最优路线。但和往常一样,回溯法的效率太低;一个n层数字三角形的完整路线有 ...
  • 数字三角形问题动态规划) Description 下图给出了一个数字三角形,请编写一个程序,计算从顶至底的某处的一条路径,使该路径所经过的数字和最大 Input 有很多个测试案例,对于每一个测试案例, 通过键盘逐行输入...
  • 很简单的动态规划,自底向上每一个地方存他下面两个分岔口较大的一个值加上它自身,一直到最顶端就是最长的路径。 状态转移方程: f[i,j] = f[i,j] + max(f[i+1,j],f[+1][j+1]) {1 , 1   #include ...
  • 动态规划的典型问题是数字三角形问题,如上图的图1所示,有一个非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数,从第一行的数开始,每次可以往左下或者右下走一格,知道...
  • 用二维数组存放数字三角形。 D(r,j) : 第r行第j个数字(r,j从...问题:求MaxSum(1,1) 1.用dp来做 D(r, j)出发,下一步只能走D(r+1 ,j)或者D(r+1, j+1)。故对于N行的三=形: if (r==N) MaxSum(r,j) = D(r,j) else MaxS...
  • *问题描述:数字三角形问题(POJ1163),求最上方数字到最下行所有路径中和最大的和 */ /*递归法*/ /* #include #include #define MAX 101 using namespace std; int D[MAX][MAX];//用来存放输入的数据 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,660
精华内容 1,064
关键字:

动态角问题