数字三角形问题详解数字三角形问题详解

数字三角形问题详解
在线提交地址请点击题目
若有任何疑问，欢迎留言 (*^_^*)
题目描述给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

7 38 810 2744 45265

输入格式第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式输出一个整数，表示最大的路径数字和。
输入样例

3 1 2 3 3 1 4

输出样例

8

数据范围 1 ≤ n ≤ 500,
? 10000 ?10000 ?10000 ≤ 三角形中的整数 ≤10000 10000 10000
解题分析
在这道题中，所需求解的原问题是：寻找一条从( 1 , 1 ) (1,1) (1,1) 到( n , j )1 ≤ j ≤ n (n,j)\ 1 \le j \le n (n,j) 1≤j≤n 的路径，使得路径上所经过数字的和最大。
第一步拆分
经过分析发现，原问题所求的是所有到达最后一行n n n 中每一个数的最大的路径当中，最大的那一条，即m a x ( f [ n , j ] )1 ≤ j ≤ n max(f[n, j])\ 1 \le j \le n max(f[n,j]) 1≤j≤n， f [ n , j ] f[n,j] f[n,j] 为到达当前位置( n , j ) (n,j) (n,j) 的最大值。
若加粗文字较难理解，请结合例子与表达式进行思考。
举个例子，如下图所示：

文章图片

【数字三角形问题详解】从( 1 , 1 ) (1,1) (1,1) 到( 3 , 1 ) (3,1) (3,1) 的最大值为6 6 6 ，从( 1 , 1 ) (1,1) (1,1) 到( 3 , 2 ) (3,2) (3,2) 的最大值为5 5 5 ，从( 1 , 1 ) (1,1) (1,1) 到( 3 , 3 ) (3,3) (3,3) 的最大值为8 8 8 。根据题意，原问题的解为从( 1 , 1 ) (1,1) (1,1) 到( 3 , 1 ) , ( 3 , 2 ) , ( 3 , 3 ) (3,1),(3,2),(3,3) (3,1),(3,2),(3,3) 中的最大路径的最大的值，故本题的解为8 8 8 。
第二步拆分
如下图所示，从i i i 行到i + 1 i+1 i+1 行有两种方式，一种是向左下走，另一种是向右下走。同理( i , j ) (i,j) (i,j) 可由( i ? 1 , j ) (i-1,j) (i?1,j) 和( i ? 1 , j ? 1 ) (i-1,j-1) (i?1,j?1) 到达。

文章图片

因此，可将第一步所拆分的子问题（m a x ( f [ n , j ] ) max(f[n, j]) max(f[n,j]) ）继续拆分成到达( i , j ) (i,j) (i,j) 的最大值f [ i , j ] f[i,j] f[i,j]。因为所求的值为最大值，若使得f [ i , j ] f[i,j] f[i,j] 最大，则需选则两种转移方案f ( i ? 1 , j ) f(i-1,j) f(i?1,j) 和f ( i ? 1 , j ? 1 ) f(i-1,j-1) f(i?1,j?1) 中值较大的一种。能够这样转移的关键在于，这道题满足最优子结构性质，即原问题所有转移方案中最优的方案，仍为原问题的最优解。
由此可以得出动态转移方程： f [ i , j ] = m a x ( f [ i ? 1 , j ] , f [ i ? 1 , j ? 1 ] ) + a [ i , j ] f[i, j] = max(f[i - 1, j], f[i - 1, j - 1]) + a[i,j] f[i,j]=max(f[i?1,j],f[i?1,j?1])+a[i,j]，其中a [ i , j ] a[i,j] a[i,j] 为( i , j ) (i,j) (i,j) 位置上的数。
参考代码
希望各位读者能够在阅读代码前独立完成

#include #include using namespace std; const int N = 510, INF = 1e9; int n, a[N][N], f[N][N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) scanf("%d", &a[i][j]); for (int i = 0; i <= n; i ++ ) for (int j = 0; j <= i + 1; j ++ ) f[i][j] = -INF; f[1][1] = a[1][1]; for (int i = 2; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]); int res = -INF; for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); printf("%d\n", res); return 0; }

本文从属于《动态规划入门指南》系列，更多动态规划问题的思维分析请点击链接查看。