FZU1004-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
Output
Sample Input
Sample Output
很明显的一道动归题,类似于求最大路径,方法有很多,搜索啊,递归啊,,,但用动归是最简单的,动归思路有两种:
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 <iostream>
#include <algorithm>
#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+,j);
int y = MaxSum(i+,j+);
return max(x,y)+D[i][j];
}
int main(){
int i,j;
cin >> n;
for(i=;i<=n;i++)
for(j=;j<=i;j++)
cin >> D[i][j];
cout << MaxSum(,) << endl;
}
如果采用递规的方法,深度遍历每条路径,存在大量重复计算。则时间复杂度为 2n, 对于 n = 100行,肯定超时。
2:记忆递归
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX]; int n;
int maxSum[MAX][MAX];
int MaxSum(int i, int j){
if( maxSum[i][j] != - )
return maxSum[i][j];
if(i==n) maxSum[i][j] = D[i][j];
else {
int x = MaxSum(i+,j);
int y = MaxSum(i+,j+);
maxSum[i][j] = max(x,y)+ D[i][j];
}
return maxSum[i][j];
}
int main(){
int i,j;
cin >> n;
for(i=;i<=n;i++)
for(j=;j<=i;j++) {
cin >> D[i][j];
maxSum[i][j] = -;
}
cout << MaxSum(,) << endl;
}
3:
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX]; int n;
int maxSum[MAX][MAX];
int main() {
int i,j;
cin >> n;
for(i=;i<=n;i++)
for(j=;j<=i;j++)
cin >> D[i][j];
for( int i = ;i <= n; ++ i )
maxSum[n][i] = D[n][i];
for( int i = n-; i>= ; --i )
for( int j = ; j <= i; ++j )
maxSum[i][j] = max(maxSum[i+][j],maxSum[i+][j+]) + D[i][j]
cout << maxSum[][] << endl;
}
人人为我”递推型动归程序
4:当然了,3中的代码也可以空间优化,从下往上找
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n; int * maxSum;
int main(){
int i,j;
cin >> n;
for(i=;i<=n;i++)
for(j=;j<=i;j++)
cin >> D[i][j];
maxSum = D[n]; //maxSum指向第n行
for( int i = n-; i>= ; --i )
for( int j = ; j <= i; ++j )
maxSum[j] = max(maxSum[j],maxSum[j+]) + D[i][j];
cout << maxSum[] << endl;
}
如果看不懂简单手推模拟一遍你就明白了,不难。。和3中代码类似,只是将二维转化为一维了;
最新文章
- WPF重写Image实现动态图片--未测试
- BZOJ 2661 连连看(费用流)
- 最全的Android源码目录结构详解
- 安装 Visual Stuidio 2010 失败
- iOS下日期的处理(世界标准时转本地时间)
- BZOJ 3992 [SDOI 2015] 序列统计 解题报告
- Android用户界面 UI组件--AdapterView及其子类(一) ListView及各种Adapter详解
- 如何发布一个自定义Node.js模块到NPM(详细步骤)
- 2016GIAC全球互联网架构大会日程分享
- Android关于AutoService、Javapoet讲解
- mysql执行计划简介
- [BZOJ]1045 糖果传递(HAOI2008)
- react-native项目中禁止截屏与录屏
- java--String equals方法
- IDEA或者WebStorm关闭JS文件的黄色提示
- 转 flowcanvas
- Yahoo的Yslow23条规则
- python开发者框架套件总结: package 包 frameworks
- javascript的实现事件的一些实例
- vue-cli 中的静态资源处理
热门文章
- ArcGIS二次开发之读取遥感图像像素值的做法
- Eclipse 闪退/无法启动/一闪而过打解决办法
- jacob的使用方法
- SQL的top 100 percent用法
- gulp自动化构建工具使用
- 获取当前目录 文件输出html 网页查看
- Android(java)学习笔记158:多线程断点下载的原理(JavaSE实现)
- java 随机数 <;%=System.currentTimeMillis() %>;
- CAD交互绘制矩形框(网页版)
- 使用jave2将音频wav转换成mp3格式