题目描述
给出一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。
规定：（1）每一步可沿左斜线向下或右斜线向下走；（2）1<三角形行数<25；（3）三角形中的数字为整数<1000；
输入
第一行为N，表示有N行
后面N行表示三角形每条路的路径权
输出
路径所经过的数字的总和最大的答案。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
这题初看似乎可以用贪心求解，但是细细一想就不可能用贪心了，因为每一行你选的最优解不代表下面一行他也是最优解，或者说再举一个例子，第一行是1，第二行是两个3，你贪心算法如何取舍呢？因此这题我们需要考虑考虑动态规划的方法，既然是动态规划，那我们先分析题目，求的是最大答案，从上往下走的最大答案，就是第一个数字加上下面两个之一的最大答案，也就是一个递推公式 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]) 以此类推。
再考虑边界问题，显然本题是从底向上的，因此要考虑最底下的边界，那就是原本的输入。
#include<iostream>
using namespace std;
int fun (int **a,int N)
{
int dp[N][N];
for(int i=0;i<N;i++)
{
dp[N-1][i]=a[N-1][i];
}
for(int i=N-2;i>=0;i--)
{
for(int j=0;j<=i;j++)
{
dp[i][j]=((dp[i+1][j]>dp[i+1][j+1])?dp[i+1][j]:dp[i+1][j+1])+a[i][j];// 请注意 这里三目运算符必须打括号！！！因为优先级最低，如果不打括号当前面表达式不符合时，得到的结果不是dp[i+1][j+1]，而是dp[i+1][j+1]+a[i][j]
}
}
return dp[0][0];
}
int main()
{
int N;
cin>>N;
int **a=new int *[N];
for(int i=0;i<N;i++)
a[i]=new int [N];
for(int i=0;i<N;i++)
{
for(int j=0;j<=i;j++)
cin>>a[i][j];
}
for(int i=0;i<N;i++)
{
for(int j=0;j<=i;j++)
cout<<a[i][j]<<" ";
cout <<'\n';
}
cout << fun(a,N);
}
