首页 / 算法 / 算法第三章上机实践报告——动态规划
算法第三章上机实践报告——动态规划
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第三章上机实践报告——动态规划,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1396字,纯文字阅读大概需要2分钟。
内容图文
1.实践题目
给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。
输入格式:
输入有n+1行:
第 1 行是数字三角形的行数 n,1<=n<=100。
接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。
输出格式:
输出最大路径的值。
输入样例:
在这里给出一组输入。例如:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
在这里给出相应的输出。例如:
30
2.问题描述
一个n行的数字三角形,每行有n个数字,从顶至低,每次只能从选择的数字的左下角或者右下角中选择一个路径往下,一直到底部考虑该路径经过的数字总和最大。
我的代码:
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n;
cin>>n;
int a[101][101];
int sum[101][101];
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++){
sum[n][i] = a[n][i];
}
for(int i=n;i>0;i--){
for(int j=1;j<=i;j++){
if(sum[i][j]>=sum[i][j+1]){
sum[i-1][j] = a[i-1][j] + sum[i][j];
}
else{
sum[i-1][j] = a[i-1][j] + sum[i][j+1];
}
}
}
cout<<sum[1][1];
}
3.算法描述
首先输入n,表示n行数字,接着用一个二维数组a[i][j]存放输入的数字,数组的行对应数字行,数组列对应数字所在行的位置,接着开始排序,先将,最后一行复制到新的一个二维数组上sum[n][i] = a[n][i],比较最后一行的第一个数和第二个数,将大的数字和上一行的第一个数相加存放到和a数组一样的位置的sum数组上,接着在比较第二个数和第三个数,再将大的数字和上一行第二个数字相加存放到sum数组上,以此类推,直到和第一行的数字相加,sum[1][1] 就是最大路径和的值。
4.时间空间复杂度
时间复杂度为O(n^2),排序时所用的二重循环,所以时间复杂度为O(n^2)。
空间复杂度:在主函数中给变量分配的空间为常数,所以空间复杂度为O(1)。
5.个人体会
在实践前,对于动态规划问题的算法还是很模糊,不知道从如何开始下手考虑问题,经历算法实践课之后,在和结对编程队友逐步讨论下慢慢解决问题,对动态规划有了更深一步的理解,但是在实现想法的过程中还是会有力不从心的感觉,还需要自身多去尝试打出代码,想出解决思路,从递归问题优化到更简单的方法,以后还需要更加努力,多加尝试,才会变得更好。
原文:https://www.cnblogs.com/ydh52/p/11708533.html
内容总结
以上是互联网集市为您收集整理的算法第三章上机实践报告——动态规划全部内容,希望文章能够帮你解决算法第三章上机实践报告——动态规划所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。