我又来发题解了（话说这是今天第几篇来着？不过都是洛谷的题目）

思路分析

$1\le r\le 1000$ 所以暴力搜索要超时 而记忆化搜索也有超时风险，所以只能考虑$DP$

要使到底部的和最大，就要肩上两个数尽可能大。也就是取肩上两个数的最大值与当前位置的数字相加，得到这个位置对应的状态

动态规划

确定状态

使用$\operatorname f$数组存状态，$\operatorname{f[i][j]}$表示从$(0,0)$走到$(i,j)$经过的数字最小的和

边界条件

$$\operatorname f[1][1]=\operatorname a[1][1];$$

状态转移方程

$$\begin{cases} \operatorname{f[i][j]}=\operatorname{max\{f[i-1][j-1],f[i-1][j]\}+a[i][j]}\\ \operatorname{ans}=\operatorname{max\{f[n][0],f[n][1]...f[n][n]\}} \end{cases} $$

(第二个是取答案最大值的)

code:

#include<iostream>
#include<algorithm>
using namespace std;
int a[1005][1005],f[1005][1005];
int main(){
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
    return 0;
}

dp

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1010][1010];
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-1;i>=1;i--)
    for(int j=1;j<=i;j++)
      a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
  cout<<a[1][1];
  return 0;
}

从下至上递推即可，对于除最后一行外的每一行的每个数都加上下方两个数中更大的那个，最后左上角的数就是答案。

#include <bits/stdc++.h>
using namespace std;
int triangle[1010][1010], n;
int main() {
    cin >> n;
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=i; j++) {
            cin >> triangle[i][j];
        }
    }
    for(int i=n-1; i>=1; --i) {
        for(int j=i; j>=1; --j) {
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
        }
    }
    cout << triangle[1][1] << endl;
    return 0;
}