数字三角形最大和 动态规划法求解 C语言

目录

题目要求

 实现代码

实验结果

题目要求

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

三角形的行数大于1小于等于100，数字为 0-99。

 实现代码

#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define MAX(x,y)(((x)>(y))?(x):(y))
const int maxn = 101;
int D[maxn][maxn];                 
int n;                             int maxSum(int i, int j){          if(i == n)                      return D[i][j];int x = maxSum(i+1,j);int y = maxSum(i+1,j+1);return MAX(x,y)+D[i][j];       
}int main(){cin >> n;for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)cin>>D[i][j];cout<<maxSum(1,1)<<endl;        return 0;
}

实验结果