精华内容
下载资源
问答
  • 给定一个由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;
     }
    
    
    展开全文
  • 动态规划 三角形最佳路径问题

    千次阅读 2017-04-18 13:08:49
    如下所示的由正整数数字构成的三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的...
    描述
    

    如下所示的由正整数数字构成的三角形:
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

    从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
    注意:路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边(右下方)的数。

    输入第一行为三角形高度100>=h>=1,同时也是最底层边的数字的数目。
    从第二行开始,每行为三角形相应行的数字,中间用空格分隔。输出最佳路径的长度数值。样例输入
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    或
    1
    8
    样例输出

    30或8


    分析:

    可以用动态规划进行分解,要倒着推,假如从第i,j开始,比较他下边和右下边的大小,大的加上,使得每一个都是最优解,最后a[1][1]就是答案;

    代码:
    #include<iostream>
    using namespace std;
    int main()
    {
       int n,i,j,a[101][101];
       cin>>n;
       for(i=1;i<=n;i++)
       for(j=1;j<=i;j++)
       cin>>a[i][j];
       for(i=n-1;i>=1;i--)
       for(j=1;j<=i;j++)
       {
       if(a[i+1][j]>=a[i+1][j+1])
       a[i][j]+=a[i+1][j];
       else
       a[i][j]+=a[i+1][j+1];
       }
       cout<<a[1][1]<<endl;
    }
    展开全文
  • 对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值。 Input 输入数据的第1行是数字三角形的行数n,1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。 O...

    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]);
    }
    

     

    展开全文
  • 有如下一个数字三角形: 73 88 1 02 7 4 44 5 2 6 5 从定点出发,在每个节点可以选择向下走或者向右下走,一直走到底层。试设计一种算法,计算从三角形顶端到底部的一条路径,是该路径...

     

    有如下一个数字三角形:

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

    从定点出发,在每个节点可以选择向下走或者向右下走,一直走到底层。试设计一种算法,计算从三角形顶端到底部的一条路径,是该路径经过的数字总和最大

     1 #include<iostream>
     2 #include<algorithm>
     3 #define NUM 101
     4 int main()
     5 {
     6     using namespace std;
     7     int n, d[NUM][NUM], *maxsum;//表示n行的数字三角形,用d数组来存放数字.
     8         cin >> n;
     9     for (int i = 1; i <= n; i++)
    10         for (int j = 1; j <= i; j++)
    11             cin >> d[i][j];
    12     maxsum = d[n];//maxsum指针指向第n行
    13     for (int i = n - 1; i >= 1; --i)
    14         for (int j = 1; j <= i; ++j)
    15             maxsum[j] = max(maxsum[j], maxsum[j + 1]) + d[i][j];
    16     cout << maxsum[1]<< endl;
    17     return 0;
    18 }

     

    ---恢复内容结束---

    转载于:https://www.cnblogs.com/tygao/p/5184960.html

    展开全文
  • 数字三角形问题 动态规划 OJ 问题:Triangle(参见 http://poj.org/problem?id=1163) 题意:在数字三角形上寻找一条沿相邻顶点从顶到底走的路径,使路径上的数字和最大。 输入:三角形高度 n,数字三角形数值。 ...
  • 动态规划——数字三角形问题 OJ问题:Triangle(参见http://poj.org/problem?id=1163) 题意:在数字三角形上寻找一条从顶到底的路径,使路径上的数字和最大。 实验方法1: 动态规划。设立二维数组d[n][n],d[i][j]...
  • 这是动态规划很经典的一个问题 就是一个三角形类似这样:  2 3 4 输出顶点的到底部的最大和,限制条件元素只能左下或者右下走 例如:上述这个三角形,这个输出就是6 解决方法:动态规划 定义的dp数组的小只需要和...
  • C++写的,利用动态规划解决数字三角形问题,含.cpp文件一个。
  • #include <bits/stdc++.h> using namespace std; int main() { int a[110][110],i,j,n,b[110][110]; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=i;j++) scanf("%d...
  • 动态规划实现数字三角形问题  (1)题目描述如图所示      (2)我们用上述矩阵分析:自顶向下分析入下图二维矩阵所示  (3)我们从arr[2][0]开始分析,arr[2][0]是计算当前位置按照题中...
  • 动态规划之数字三角形问题

    千次阅读 2020-08-05 17:01:35
    问题描述 在数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或者右下走。只需要求出这个最大和即可。不必给出具体路径。 三角形的行数大于1小于等于100,数字...
  • 设计一个算法,计算出从三角形的顶到底的一条路径,使该路径经过的数 字总和最大。例如,上述数字三角形的最优解 30 ,自顶向下的路径为 7-3-8-7-5。 数据输入: 由文件 input.txt 提供输入数据。 文件的第 1 行是...
  • 动态规划-数字三角形问题

    万次阅读 多人点赞 2018-11-04 19:23:44
    有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数.  1  3 2  4 10 1 4 3 2 20 从第一行的数开始,每次可以往左下或右下走一格,直到走到最下行,把沿途...
  • 数字三角形问题 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大...
  • 动态规划的典型问题是数字三角形问题,如上图的图1所示,有一个非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数,从第一行的数开始,每次可以往左下或者右下走一格,知道...
  • 数字三角形问题 Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 对于给定的由n行数字组成的数字三角形,计算从...
  • *问题描述:数字三角形问题(POJ1163),求最上方数字到最下行所有路径中和最大的和 */ /*递归法*/ /* #include #include #define MAX 101 using namespace std; int D[MAX][MAX];//用来存放输入的数据 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 917
精华内容 366
关键字:

动态规划三角形问题