实践报告——第一题
1、实践题目
数字三角形
2、问题描述
给定一个由 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
3、算法描述
这是道动态规划的题目，使用动态规划的思想，把问题一步一步细分，寻找子问题的最优解。
对这道题来说，子问题就是从最底下的相邻数字的和算起，即一步一步往上运算，每一步都满足最小这个条，到第一行的时候就是最后的解。
实现这一操作则需要归纳出递归方程：
Max[i][j] = A[i][j]+max（Max[i+1][j]，Max[i+1][j+1]）
然后进行填表操作，二维数组，自下而上，自左往右。
4、算法时间及空间复杂度分析
时间复杂度：o(n*n)，填表时使用了二维数组，则用到了两层循环，所以时间复杂度是n的平方。
空间复杂度：在主函数中，给变量分配的空间为常数，所以空间复杂度为o（l）。
5、心得体会
第一次接触动态规划，有点难理解，没怎么会往那个方向去想题目。然后慢慢看题目，不知道怎么得出递归方程，最后和同伴数学分析，慢慢尝试，用数学运算得出了规律，最后得出了递归方程，就开始用动态规划的套路实现这个递归方程了。最后做出之后挺有成就感的，这次和小伙伴配合很棒，大家有各自的思考，可以互补对方思考的空缺。虽然这次一节课只完成了这一道题，但这也算是动态规划的典型例子了，还是很有成就感的。应该课后多点实践，缺少刷题，对动态规划的熟悉还不够。
#include<iostream>
using namespace std;
int main(){
int n,a=1;
cin>>n;
int A[101][101];
for(int i = 1;i<=n;i++){
for(int j=1;j<=n;j++){
A[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=a;j++){
cin>>A[i][j];
}
a++;
}
int Max[101][101];
for(int j=1; j<=n; j++){
Max[n][j]=A[n][j];
}
for(int i=n-1; i>0; i--){
for(int j=1; j<=i; j++){
if((Max[i+1][j+1])<Max[i+1][j]){
Max[i][j] = A[i][j]+Max[i+1][j];
}
else Max[i][j] = A[i][j]+Max[i+1][j+1];
}
}
cout<<Max[1][1];
return 0;
}
算法第三章上机实践报告——动态规划
原文：https://www.cnblogs.com/ErwinG/p/11710310.html
