数字三角形
例题一、数字三角形 (POJ1163)
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的数字三角形中寻找一条从顶部到底边路径,使得 路径上所经过的数字之和最大。每一步都只能往左下或右下走。只需要求出这个最大和即可,不必给具体路径。
三角形的行数大于 1小于 等100 ,数字为 0 -99
输入格式:
5 // 三角形行数。下面是三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
1. 递归
直接使用递归的话,因为重复计算,时间效率很低
2. 递推计算
1 | int i,j; |
3. 记忆化搜索
D[i][j]的初始值设为-1,memset(D,-1,sizeof(D));
递归函数:
1 | int MaxSum(int i,int j){ |
4. 空间优化
(1)方法一
没必要用二维maxsum数组储存每一个MaxSum(i,j),只要从底层一行行向上递推,那么只要一维数组maxsum[100]即可,只要储存一行的MaxSum值就可以。
即计算第i行的MaxSum(i.j)时,在不影响计算的情况下,覆盖第i+1行的MaxSum(i,j)。
1 | for(int i=1;i<=n;i++) |
(2)方法二
不使用maxsum数组,直接用D[n]代替。
完整代码:
1 |
|