题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数n,表示数字三角形的层数。
接下来n行,每行包含若干整数,其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数,表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
样例
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
算法:线性DP
DP问题我们需要从状态表示和状态转移来思考这个问题
这一题我们可以从行列来枚举每个状态
DP[i][j]表示的是从顶点出发所有到达第i行第j列的选法
DP[i][j]中存储的是所有选法中的最大值
然后我们可以推导DP[i][j]的转移方程
DP[i][j]只能从它左上或者右上的点转移过来
所以 DP[i][j]=max(DP[i-1][j],DP[i-1][j-1])+q[i][j];
然后为了防止边界问题我们需要给DP数组进行初始化
最后的答案就是最后一行中的最大值
时间复杂度O(n^2)
C++ 代码
#include"iostream"
#include"algorithm"
using namespace std;
const int N=510;
int q[N][N],dp[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)cin>>q[i][j];
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)dp[i][j]=-1e9;
dp[1][1]=q[1][1];
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i-1][j-1]+q[i][j],dp[i-1][j]+q[i][j]);
int res=-1e9;
for(int i=1;i<=n;i++)res=max(res,dp[n][i]);
cout<<res;
return 0;
}
JU