本代码由蒟蒻牌蒟蒻提供，仅供新手，大佬勿喷 谁都会部分，输入 如果你看懂了，那恭喜你，没卵用。 接下来就开课了 动态规划（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)，这被称为动态转移方程 代码： 最后输出： 完整代码 看到这了，点个赞呗！

#include<iostream> using namespace std; int a[1005][1005]; 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>0;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; } 比如说: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 倒数第二行： 第一个2下面是4 5 5>4 2+=5 变为： 7 3 8 8 1 0 7 7 4 4 4 5 2 6 5 7下面是5 2 5>2 7+=5 变为： 7 3 8 8 1 0 7 12 4 4 4 5 2 6 5 以此类推 按以上操作从倒数第二行一直操作到第一行 最后第一行第一个即为答案

没啥可讲的 动态规划解决、 代码： #include<bits/stdc++.h> using namespace std; int r; int a[105][105]; int main(){ cin >> r; for(int i = 0;i < r;i ++){ for(int j = 0;j <= i;j ++){ cin >> a[i][j]; } } for(int i = r-2;i >= 0;i --){ for(int j = 0;j <= i;j ++){ a[i][j] += max(a[i+1][j] , a[i+1][j+1]); } } cout << a[0][0]; return 0; }

#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]; }

CP003174 DP题解 这道题是经典的动态规划题目，有三种方法来做： * 搜索（超时） * 记忆化搜索 * 动态规划 在这里，本人主要介绍动态规划（Dymanic Programming,DP）的做法。 1. 确定状态：本题题目使用二维数组，故状态为dp[i][j]。 2. 确定状态转移方程：所有的dp元素都是由该元素下面的两个元素的权值中的最大权值加上自己，故其状态转移方程便是：dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]); 3. 确定边界条件：该图的底层是最下面的一行元素，从倒数第2行往上递推即可。 4. 程序实现：

#include <bits/stdc++.h> #define debug freopen("in.txt","r",stdin);freopen("out.txt","w",stdout) #define N 105 using namespace std; int n,maxv; int a[N][N],dp[N][N]; void work() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; if(i==n) maxv=max(maxv,dp[i][j]); } cout<<maxv; } int main() { //debug; work(); return 0; }

#include<bits/stdc++.h> using namespace std; int a[1001][1001]; 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>0;i--){ for(int j=1;j<=n;j++){ a[i][j] = max(a[i+1][j+1]+a[i][j],a[i+1][j]+a[i][j]); } } cout<<a[1][1]; }

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

找到路径最大,用max,即可解决啊 a[i][j]+=max(a[i+1][j],a[i+1][j+1]); 则可以解决[上面的人给了点建议哈] 上代码:

#include <iostream> #include <algorithm> using namespace std; int a[105][105]; int main() { int n; cin>>n; for (int i=1;i<=n;i++) { for (int j=1;j<=i;j++) { scanf("%d",&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 dp[1005][1005],n; int main(){ 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<<dp[1][1]; return 0; }

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

#include <bits/stdc++.h> using namespace std; const int inf = 1e9; int a[107][107]; int dp[107][107]; int n; int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cin >> a[i][j]; dp[i][j] = -inf; } } dp[1][1] = a[1][1]; for (int i = 1; i < n; i++) { for (int j = 1; j <= i; j++) { dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i + 1][j]); dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i + 1][j + 1]); } } int ans = -inf; for (int i = 1; i <= n; i++) { ans = max(ans, dp[n][i]); } cout << ans; }