专栏首页小L的魔法馆动态规划(一)POJ1163

动态规划(一)POJ1163

动态规划算法是比较实用的算法之一,结合实际问题能更好的熟悉这个算法 下面以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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 断言assert()与调试帮助

    对expr求值,如果expr为假,则输出信息并终止程序,反之则什么也不做。 用来检查”不会发生”的条件。 assert的行为依赖与NDEBUG的预处理变...

    Enterprise_
  • C++的队列和pair

    pair类型: 一般当一个对象有多个属性的时候,我们会用结构体stuct写多个属性,而当只有两个属性的时候,就可以使用pair. 使用方法:

    Enterprise_
  • BFS练习-POJ.2386

    Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions...

    Enterprise_
  • Pytest之并发执行(十四)

    不管是UI自动化测试用例还是API的自动化测试用例,在编写的使用都需要注意每个测试用例执行的独立性,也就是说编写的每个测试用例都是互相不依赖的,这...

    无涯WuYa
  • AkShare-债券数据-可转债

    目标地址: http://vip.stock.finance.sina.com.cn/mkt/#hskzz_z

    AkShare
  • 关于CVE-2019-13272 linux本地提权的复现经历

    用户5878089
  • Cannot open picture in content server

    we are facing a problem with CRM Content Management. Currently we're using atta...

    Jerry Wang
  • Python数据处理从零开始----第三章(pandas)④数据合并和处理重复值目录数据合并移除重复数据

    ===============================================

    用户1359560
  • 高并发编程-Condition深入解析

    Condition接口位于java.util.concurrent.locks包下,实现类有 AbstractQueuedLongSynchronizer.Co...

    JavaQ
  • 2020CVPR | ATSS——最新技术的目标检测(文末源码下载)

    今天我们从录用的CVPR2020文章中选了一篇目标检测的优秀文章:ATSS:Bridging the Gap Between Anchor-based and ...

    计算机视觉研究院

扫码关注云+社区

领取腾讯云代金券