首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >动态规划(一)POJ1163

动态规划(一)POJ1163

作者头像
Enterprise_
发布2019-02-21 17:18:58
5030
发布2019-02-21 17:18:58
举报
文章被收录于专栏:小L的魔法馆小L的魔法馆

动态规划算法是比较实用的算法之一,结合实际问题能更好的熟悉这个算法 下面以POJ1163为例子

1. 首先是题目大意

:在给定的一个数字三角形中找到一条自上而下的路径,路径每一步只能左下或者右下,最后使得这条路径上的数字之和最大 Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30

2.题目分析

如果使用DFS从最上面的点来进行深度遍历,简单计算一下,拿上面的数字三角形来举例,会计算经过第三行的7的路径3次,最后一行的2是6次,这样存在大量的重复计算,在规定的时间里算不出来的。所以引出动态规划算法

  • 它的思想是我们从终点向起点回退,这样把求解过程分解,每一步里面对应的子问题的终点不变,但是起点会逐渐向上移动,使得上一步已经求解的问题恰好是下一步新问题的子问题,到了最后一步,求解最大的子问题就是原始问题。

放在这一题上怎么做呢?

这里写图片描述
这里写图片描述

- 首先,把所有的数字存入一个ap的二维数组中,先假定Max(x,y)表示以x,y这一个数字为起点(即ap[x][y])到可能终点里面,最大的路径数字之和。 - 接下来开始回推了,从底边开始,底边到终点自然就是本身了,接着上一行的2开始到底边就可以选择了,如果左下,那么和就是6,右下就是7,所以选择右下,即Max(4,1)=7,同理可知道Max(4,2)=12,Max(4,3)=10,Max(4,4)=10. - 在这里,一般把当前子问题及其解成为一个状态,所以记录下当前子问题的解,是为了后面求解时使用,也就是下一个状态的发生,而从上面的推导可以找到这样的一个关于子问题目标函数的最大值之间依赖关系,也就是常说的状态转移方程 Max[i][j] = max(Max[i + 1][j], Max[i + 1][j + 1]) + ap[i][j]; -

这里写图片描述
这里写图片描述

3.代码如下

#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
    int Max[105][105], ap[105][105],i,j,n;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
            cin >> ap[i][j];
    for (j = 1; j <= n; j++)
        Max[n][j] = ap[n][j];
    for (i = n - 1; i >= 1; --i)
        for (j = 1; j <= i; ++j)
            Max[i][j] = max(Max[i + 1][j + 1], Max[i + 1][j]) + ap[i][j];
    cout << Max[1][1] << endl;
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年03月10日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 首先是题目大意
  • 2.题目分析
  • 3.代码如下
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档