蓝桥杯——算法训练——数字三角形蓝桥杯

蓝桥杯——算法训练——数字三角形这道题不难，但是比较典型，可以作为动态规划（dp）的入门篇，属于线性dp（LIS，LCS和数字三角形都是此类题型）。
——————————————————————————————
问题描述
（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走；
●1＜三角形行数≤100；
●三角形中的数字为整数0，1，…99；

文章图片

（图３.１－１）
输入格式
文件中首先读到的是三角形的行数。
接下来描述整个三角形
输出格式
最大总和（整数）
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
时间限制：1.0s 内存限制：256.0MB
——————————————————————————————
思路分析：这道题拿到手，可能会有人想到枚举，把所有的路线结果列举出来，再比较大小不就行了，但是这样做的后果很可能就是超时，因为一旦三角形的规模上去了，排列组合的情况就会暴涨。所以这里不妨采取递推的想法，从底部开始记录，运用动态规划的想法（追求子问题的最优解），逐步向上更新数字三角形的值，最终的答案就是塔顶的值，看代码：

#include #include #include #include//包含max()函数的头文件 using namespace std; int num[101][101]; //记录数塔 int main(){ int n; while(scanf("%d", &n) != EOF){ memset(num, 0, sizeof(num)); //初始化数塔 for(int i=1; i<=n; i++){ for(int j=1; j<=i; j++){ scanf("%d", &num[i][j]); //数塔初值 } } for(int i=n-1; i>=1; i--){ //注意是从倒数第二层开始更新的（最后一层没有必要） for(int j=1; j<=i; j++){ num[i][j] += max(num[i+1][j], num[i+1][j+1]); //dp方程，来历可以自己先想想，文末是个人想法 } } printf("%d\n", num[1][1]); } return 0; }

【蓝桥杯——算法训练——数字三角形】dp方程：
我们可以先从特殊情况来考虑本题，这道题最大的变数就在于数塔的层数，那么这就是突破口：
1、假设数塔只有一层，答案很显然
2、假设数塔有两层，那么就将第二层大一点的值增加到第一层，求得答案
3、假设数塔有三层，按照代码的思路，先更新倒数第二行，我们一个值一个值的更新，每一个值结合下面一层都会有自己的两层小数塔，