DP解法

每一条路的最优解都可以看作该点(分支的最优解+该点)的较大值

Tips: 数据范围是5 (确信)

#include <bits/stdc++.h>
using namespace std;

const int N = 500;

int dp[N][N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> dp[i][j];
    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]);
    cout << "max=" << dp[1][1] << endl;
    return 0;
}

方法一：暴力搜索dfs

我们可以从(1,1)走到(x,y)，计算经过的路径和，枚举x,y，更新最大值，得到答案 时间复杂度：$O(2^n)$，可能超时，但是OJ能过；记忆化搜索剪枝时间复杂度可以降到$O(n^2)$ 代码（未剪枝）：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int w[maxn][maxn],f[maxn][maxn],ans,n;
void dfs(int x,int y,int cur)//x,y表示坐标，cur表示路径最大和
{
    //递归边界
    if(x==n)
    {
        //更新最大值
        ans=max(ans,cur);
        return;
    }
    dfs(x+1,y,cur+w[x+1][y]);
    dfs(x+1,y+1,cur+w[x+1][y+1]);
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin >> w[i][j];
    dfs(1,1,w[1][1]);
    cout << "max=" << ans;
    return 0;
}

方法二：动态规划

思路不解释了，直接上代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int f[maxn][maxn],w[maxn][maxn];
int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin >> w[i][j];
    f[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+w[i][j];
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[n][i]);
    cout << "max=" << ans;
    return 0;
}