算法设计与分析----动态规划之数字三角形问题_数字三家形问题算法

题目：

在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为 0 - 99。

利用动态规划自底而上求解。

#include<bits/stdc++.h>
using namespace std;
int dp[100][100];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j = 1;j<=i;j++)
			scanf("%d",&dp[i][j]);
	for(int i=n-1;i>=1;i--)
		for(int j=1;j<=i;j++)
			dp[i+1][j]+dp[i][j]>=dp[i+1][j+1]+dp[i][j]?dp[i][j]=dp[i+1][j]+dp[i][j]:dp[i][j]=dp[i+1][j+1]+dp[i][j];
	printf("%d",dp[1][1]);
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15