做题总结——数字三角形
题目
题意分析：
这道题目就是寻找从上至下数值最大的一条路线(与“杨辉三角”十分类似)
做题思路：
这道题目利用贪心算法肯定是错误的！
先介绍一种解法。这道题目可以利用“杨辉三角”的思路，根据一个上面的元素与下面两个元素的递推公式(在动态规划里面称作状态转移方程)，从下至上地解决此问题(详细思路以后再补)
代码实现
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int main()
{
int n,a[1010][1010],i,j; //这里地二维数组空间一定要开的足够大
cin>>n;
for(i=1;i<=n;i )
{
for(j=1;j<=i;j )
{
cin>>a[i][j];
}
}
/*if(n==1)
{
cout<<a[1][1]<<endl;
return 0;
}*/
for(i=n-1;i>=1;i--) //按照递推公式(状态转移方程)进行实现
{
for(j=1;j<=i;j )
{
a[i][j] =max(a[i 1][j],a[i 1][j 1]);
}
}
cout<<a[1][1]<<endl;
}
