数字三角形
题目
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
动态规划
题目分析
此题考查简单的线性dp,直接倒叙dp,干就完了;
状态表示
f[i][j]表示底部向上或者左上移动时,在(i,j)处的最大数字和;
状态转移
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j](此点的数字);
C++代码
#include<iostream>
using namespace std;
const int N=520;
int a[N][N];
int f[N][N];
int main()
{
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=n;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
}
}
cout<<f[1][1]<<endl;
return 0;
}
此题较为简单,就不写注释了