解题思路:动态规划,将输入的三角形数值存入数组,由题意:每一步只能由当前位置向左下或右下可得在数组中只能从下或右下走,因此从倒数第二行(倒数第一行下面没有元素)元素dp[i][j]计算时,dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i+1][j+1])即本身的值加下与右下值中最大的.以此类推第一个元素dp[0][0]的值就是所求最大路径的值.
注意事项:动态规划,数组,从下往上
参考代码:
#include<bits/stdc++.h> using namespace std; int main(){ int n,line,i,j; cin>>n; while(n--){ cin>>line; vector<vector<int>> trangle(line,vector<int>(line,0));//初始化数组 for(i=0;i<line;i++){ for(j=0;j<=i;j++){ cin>>trangle[i][j];//给三角形对应位置赋值 } } for(i=line-2;i>=0;i--){ for(j=0;j<=i;j++){ trangle[i][j]+=max(trangle[i+1][j],trangle[i+1][j+1]);//当前值加等于下方和右下方元素当中的最大值 } } cout<<trangle[0][0]<<endl; } return 0; }
0.0分
3 人评分
DNA (C++代码)浏览:651 |
C二级辅导-统计字符 (C语言代码)浏览:751 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:711 |
C语言训练-阿姆斯特朗数 (C语言代码)浏览:866 |
矩阵转置 (C语言代码)浏览:1529 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1886 |
C语言训练-素数问题 (C语言代码)浏览:1000 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:277 |
C语言程序设计教程(第三版)课后习题6.6 (C++代码)浏览:634 |
水仙花 (C语言代码)浏览:1095 |