上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和(路径上的每一步只可沿左斜线向下或右斜线向下走)。
第一行包括一个整数N,表示有N行,接下来输入数字三角形 输入例子: 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出: 30#include<bits/stdc++.h> using namespace std; int main(){ int f[200][200]; int a[200][200]; int n; cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]); } } int m=f[n][1]; for(int i=1;i<=n;i++){ if(m<f[n][i]){ m=f[n][i]; } } cout<<m; return 0; }关键是: 利用数组进行类似递归的操作,用上一步的最大值来推下一步。 标签:200,数字,--,路径,int,三角形,动态 From: https://www.cnblogs.com/luckyyaoyao/p/17975161