题目描述
经典的数字三角形问题
算法1
(动态规划) $O(n^2)$
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+arr[i][j]
时间复杂度
注意事项
将边界设置为-0x3f3f3f3f;
这样边界情况不需要特别判断
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=600;
int arr[maxn][maxn];
int dp[maxn][maxn];
int main()
{
memset(arr,0x3f,sizeof arr);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>arr[i][j];
}
}
for(int i=0;i<=maxn;i++)
{
for(int j=0;j<=maxn;j++)
{
dp[i][j]=-0x3f3f3f3f;
}
}
dp[1][1]=arr[1][1];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+arr[i][j];
}
}
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
res=max(res,dp[n][i]);
}
cout<<res<<endl;
return 0;
}