【前言】
今天是刷题打卡第62天！
记得加油哦。
原题：数字三角形（递推、简单DP）
题目描述：
输入格式：
第一个行一个正整数 n ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式：
单独的一行,包含那个可能得到的最大的和。
数据范围：
1 ≤ n ≤ 1000，三角形数字值在 [0,100] 范围内。
示例:
输入：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出：
30
思路：
本题采用倒推的方式：
假设func[i][j]表示的是从 i, j 到最后一层的最大路径之和
当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择是沿其下两条可行路径中最大数字的方向前进，所以找出递推关系：func[i][j] += max(func[i+1][j],func[i+1][j+1])；
注意：func[i][j]表示当前数字的值，func[i+1][j]和func[i+1][j+1]分别表示从i+1,j、i+1,j+1到最后一层的最大路径之和；
最终func[0][0]就是所求
代码执行：
#include<stdio.h> #include<algorithm> using namespace std; int func[1005][1005] = {0}; int main() { int n = 0; scanf("%d", &n); int i = 0; int j = 0; for(i = 0; i < n; i++) { for(j = 0; j <= i; j++) { scanf("%d", &func[i][j]); } } //假设func[i][j]表示的是从i, j到最后一层的最大路径之和 //找出递推关系：func[i][j]+=max(func[i+1][j],func[i+1][j+1]); //func[i][j]表示当前数字的值，func[i+1][j]和func[i+1][j+1]分别表示从i+1,j、i+1,j+1到最后一层的最大路径之和 //最终func[0][0]就是所求 for(i = n - 2; i >= 0; i--) { for(j = 0; j <= i; j++) { func[i][j] += max(func[i+1][j], func[i+1][j+1]); } } printf("%d\n", func[0][0]); return 0; }
结语
今天是刷题打卡第62天！
加油吧少年。
