题目选自https://www.lanqiao.cn/courses/31015/learning/?id=1926986

这个题目虽然跟正常的数字三角形一样使用dp动态规划做的，但是在题目的最后一行提到左右选择的次数差要小于一；
那么也就是说我们自顶向下找，设立一个数组dp[i][j]用来存放已到达i行j列的最优解。

找完n行之后我们得到n行j列的每个最优解dp[n][j]；

此时的dp数组并未考虑左右步长之差不能超过1不符合条件；
如何才能使我们得到符合条件呢？

既然左右步长之差不能超过一就从最后一例最优解vis[n][j]中找中间的列数的最优解。

也就是说 要想要左右步数不能超过一 那么必然在中间取到 因为|左步数-右步数|< =1;
若n为偶数 即步数为奇数 此时|左步数-右步数|= =1 即在第n行中间两个数（(n/2),(n/2)+1）取；
若n为奇数 即步数为偶数 此时|左步数-右步数|= =0 即在第n行中间取（n/2+1）；

include<bits/stdc++.h>

using namespace std;
int arr[101][101];
int dp[101][101];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>arr[i][j];
}
}
dp[1][1]=arr[1][1];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(j = = 1)dp[i][j]=dp[i-1][j]+arr[i][j];
else if(j = = i)dp[i][j]=dp[i-1][j-1]+arr[i][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+arr[i][j];
}
}
if(n%2==1){
cout<<dp[n][n/2+1];
}
else{
cout<<max(dp[n][n/2],dp[n][n/2+1]);
}
return 0;
}

此篇文章为在下的第一篇博客，可能写的不是那么明了，如果有更好的方法或观点请指教。