数字三角形问题 动态规划
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行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
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行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

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]表示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;
}