水题，DP解决

本代码由蒟蒻牌蒟蒻提供，仅供新手，大佬勿喷

谁都会部分，输入

#include<bits/stdc++.h>//自由万能头
using namespace std;
int dp[1005][1005];//二维数组存储
int main(){
	int r;
	cin>>r;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=i;j++){
			cin>>dp[i][j];
		}
	}

如果你看懂了，那恭喜你，没卵用。

接下来就开课了
动态规划（Dynamic Programming，简称DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 。

再回来看题目，以样例为例，要求最大路径，如果用贪心从上往下搞，路径应为7-8-1-7-5，并非最优策略。

但当我们从局部来看，如左下角的
2
4 5
傻子都知道选5，在这时候和为2+5=7，这就是最优解。而如果我们把整体拆成这样的一个个子任务，再往上到最上面，问题就迎刃而解了。

从倒数第二行开始遍历，这时候f(x,y)=max((f(x+1,y),f(x+1,y+1))+f(x,y)，这被称为动态转移方程

代码：

for(int i=r-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<<dp[1][1];//最顶端

完整代码

#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
	int r;
	cin>>r;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=i;j++){
			cin>>dp[i][j];
		}
	}
	for(int i=r-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<<dp[1][1];
}

看到这了，点个赞呗！