博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
FZU1004-Number Triangle经典动归题,核心思路及代码优化
阅读量:5296 次
发布时间:2019-06-14

本文共 3226 字,大约阅读时间需要 10 分钟。

 

Problem 1004 Number Triangle

Accept: 2230    Submit: 5895
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

          7
       3   8
     8  1  0
   2  7  4  4
 4  
5  2   6  5
 

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

 Input

There are multiple test cases.The first line of each test case contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

 Output

Print a single line containing the largest sum using the traversal specified for each test case.

 Sample Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 Sample Output

30

   很明显的一道动归题,类似于求最大路径,方法有很多,搜索啊,递归啊,,,但用动归是最简单的,动归思路有两种:

   1:

用二维数组存放数字三角形;

D( r, j) : 第r行第 j 个数字(r,j从1 开始算)

MaxSum(r, j) : 从D(r,j)到底边的各条路径中最佳路径的数字之和,问题是就求MaxSum(1,1);

典型的递归问题
D(r, j)出发,下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形:
if ( r == N)
MaxSum(r,j) = D(r,j)
else
MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j);

2: 如果每算出一个MaxSum(r,j)就保存起来,下次用到其值的时候直接取用,则可免去重复计算。

那么可以用 O(n2)时间完成计算。因为三角形的数字总数是 n(n+1)/2;这时,递归转化为递推;

 

 下面呈现两种思路代码:

  1:超时代码:       

#include 
#include
#define MAX 101 using namespace std; int D[MAX][MAX]; int n;int MaxSum(int i, int j){ if(i==n)return D[i][j]; int x = MaxSum(i+1,j); int y = MaxSum(i+1,j+1); return max(x,y)+D[i][j];}int main(){ int i,j; cin >> n; for(i=1;i<=n;i++)for(j=1;j<=i;j++) cin >> D[i][j]; cout << MaxSum(1,1) << endl;} 如果采用递规的方法,深度遍历每条路径,存在大量重复计算。则时间复杂度为 2n, 对于 n = 100行,肯定超时。

 

  2:记忆递归

#include 
#include
using namespace std;#define MAX 101int D[MAX][MAX]; int n;int maxSum[MAX][MAX];int MaxSum(int i, int j){ if( maxSum[i][j] != -1 ) return maxSum[i][j]; if(i==n) maxSum[i][j] = D[i][j]; else { int x = MaxSum(i+1,j); int y = MaxSum(i+1,j+1); maxSum[i][j] = max(x,y)+ D[i][j]; } return maxSum[i][j];}int main(){ int i,j; cin >> n; for(i=1;i<=n;i++)for(j=1;j<=i;j++) { cin >> D[i][j]; maxSum[i][j] = -1;} cout << MaxSum(1,1) << endl;}

 

  3:

#include 
#include
using namespace std;#define MAX 101int D[MAX][MAX]; int n;int maxSum[MAX][MAX];int main() { int i,j; cin >> n; for(i=1;i<=n;i++)for(j=1;j<=i;j++) cin >> D[i][j]; for( int i = 1;i <= n; ++ i ) maxSum[n][i] = D[n][i]; for( int i = n-1; i>= 1; --i )for( int j = 1; j <= i; ++j ) maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j] cout << maxSum[1][1] << endl;} 人人为我”递推型动归程序

 

 4:当然了,3中的代码也可以空间优化,从下往上找

    

#include 
#include
using namespace std;#define MAX 101int D[MAX][MAX];int n; int * maxSum;int main(){ int i,j; cin >> n; for(i=1;i<=n;i++)for(j=1;j<=i;j++) cin >> D[i][j]; maxSum = D[n]; //maxSum指向第n行 for( int i = n-1; i>= 1; --i )for( int j = 1; j <= i; ++j ) maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j]; cout << maxSum[1] << endl;} 如果看不懂简单手推模拟一遍你就明白了,不难。。和3中代码类似,只是将二维转化为一维了;

 

转载于:https://www.cnblogs.com/nyist-TC-LYQ/p/5292981.html

你可能感兴趣的文章
系统安全-Firewall
查看>>
c++11 : Local and Unnamed Types as Template Arguments
查看>>
Vue2 学习笔记5
查看>>
adb链接时报错误10061解决方法
查看>>
7834:分成互质组
查看>>
开餐馆
查看>>
09:密码翻译
查看>>
ES6语法:let和const
查看>>
ranch分析学习(四)
查看>>
Android电池电量更新 - BatteryService(转)
查看>>
HTML5 APP
查看>>
阿里云ecs环境配置
查看>>
python的sorted相关
查看>>
alt-opt and end2end
查看>>
线程间通信
查看>>
Goroutine陷阱
查看>>
mws文件中的tab文件改为相对路径
查看>>
C语言学习日记6
查看>>
LuoGu P2735 电网 Electric Fences
查看>>
BZOJ 1246 & 有点不一样的概率DP
查看>>