题目描述
=
#include<iostream>
using namespace std;
const int N=505;
int dp[N][N]; //到达点(i,j)的最大路径和
int w[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>w[i][j];
}
}
for(int i=1;i<=n;i++)
{
dp[n][i]=w[n][i];
}
for(int i=n-1;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+w[i][j];
}
}
cout<<dp[1][1];
return 0;
}
深搜
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 505; // 根据数据范围设置最大值
int a[N][N];
int n;
int dfs(int x,int y)
{
if(x==n) //递归终止条件
{
return a[x][y];
}
return a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));
}
int main() {
cin >> n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
cout<<dfs(1,1);
return 0;
}
记忆化搜索
#include <iostream>
#include <vector>
#include <algorithm>
#include<cstring>
using namespace std;
const int N = 505; // 根据数据范围设置最大值
int a[N][N],memo[N][N];
int n;
int sum;
int dfs(int x,int y)
{
if(memo[x][y]!=-1)
{
return memo[x][y]; //如果该节点之前搜索过,则直接拿取记忆
}
if(x==n) //递归终止条件
{
return a[x][y];
}
memo[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));
return memo[x][y];
}
int main() {
cin >> n;
memset(memo,-1,sizeof(memo));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
cout<<dfs(1,1);
return 0;
}
=