动态规划——数塔问题
2018-06-18 04:01:42来源:未知 阅读 ()
从数塔顶层出发,每个结点可以选择向左走或向右走,要求一直走到塔底,使得走过的路径上的数值和最大。
#include <iostream> #include <cstdio> using namespace std; const int N = 100; // 下面这个函数实现的是更新最大值,o赋值为o和x的最大值 template <class T> void updateMax(T& o, const T& x) { o = (o > x) ? o : x; } // f数组为动态规划的状态数组 // num数组为读入的数塔 // n为读入的数塔高度 int f[N][N], num[N][N], n; int main() { // 读入n和数塔数组num scanf("%d", &n); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { scanf("%d", &num[i][j]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ //从上到下 用另一个数组储存走到当前最大的值 updateMax(f[i][j],max(f[i - 1][j],f[i - 1][j - 1])+num[i][j]); } }// step 1 begin: 在这里实现动态规划算法逻辑 // step 1 end. // 定义最终结果变量result,因为是计算最大值,所以初始化为0 int result = 0; for (int i = 1; i <= n; ++i) {//因为上一个循环已经计算了值 所以可以直接在最后一层查找 // step 2 begin: 在这里实现更新最终结果的逻辑 updateMax(result,f[n][i]);//是赋值而不是交换 记住啦!!!!!! // step 2 end. } // 输出最终最大权值和result printf("%d\n", result); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
- 用C++实现:完美的代价 2020-04-15
- [题记-动态规划] 编辑距离 - leetcode 2020-04-06
- 用C++实现:FJ的字符串打印 2020-04-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash