C++数字三角形问题与dp算法

题目：数字三角形

题目介绍：如图所示的数字三角形，要求从最上方顶点开始一步一步下到最底层，每一步必须下一层，求出所经过的数字的最大和。

输入：第一行值n，代表n行数值；后面的n行数据代表每一行的数字。

输出：经过数字的最大和。

例：

输入：

4

1

3 2

4 10 1

4 3 2 20

输出：

24

分析：这也是一个典型的贪心算法无法解决的问题，同样可以用动态规划（dp算法）来解决。把边界数字首先初始化到结果矩阵中，再根据状态方程完成结果矩阵的遍历。需要注意的就是数组不是矩形而是三角形，与传统的状态方程相比需要做点改进。

数组编号：

状态方程：p[ i ][ j ]=max{ p[ i-1 ][ j-1 ] , p[ i-1 ][ j ]}

代码如下：

#include <iostream>
using namespace std;
int main()
{
  int i;
  int n;
  cin >> n;
  int **p = new int *[n];
  for (i = 0; i < n; i++)
  {
    p[i] = new int[n];
  }
  for (i = 0; i < n; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      cin >> p[i][j];
    }
  }
  for (i = 1; i < n; i++)
  {
    p[i][0] += p[i - 1][0];
  }
  for (i = 1; i < n; i++)
  {
    p[i][i] += p[i - 1][i - 1];
  }
  for (i = 2; i < n; i++)
  {
    for (int j = 1; j < i; j++)
    {
      p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j];
    }
  }
  for (i = 0; i < n; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      cout << p[i][j] << " ";
    }
    cout << endl;
  }
}

结果如下图：

所以最下层的数字和最大值是24.

总结

以上所述是小编给大家介绍的C++数字三角形问题与dp算法，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的！

赞 (0)

相关推荐

  • 详解C++ 动态内存分配与命名空间

    1.C++中的动态内存分配 通过new关键字进行动态内存申请 C++中的动态内存申请时基于类型进行的 delete关键用于内存释放 C语言其实是不支持动态内存分配的,是通过malloc库函数来实现的,可能有一些硬件根本不支持malloc:而C++ new是一个关键字,不管在任意编译器上,任意硬件平台上都是能够进行动态内存分配的,这是本质区别. malloc是基于字节来进行动态内存分配的,new则是基于类型来进行动态内存分配 // 变量申请: Type * pointer = new Type;

  • 浅析Java、C/C++、JavaScript、PHP、Python分别用来开发什么?

    首先,我们先普及一下编程语言的基础知识.用任何编程语言来开发程序,都是为了让计算机干活,比如编写一篇文章,下载一首MP3等,而计算机干活的CPU只认识机器的指令,所以,尽管不同的编程语言差异极大,最后都得"翻译"成CPU可以执行的机器指令.理论上任何语言干任何事情几乎都可以, 但是主要干什么那就不一样了. 01.Java java常常跟"企业"联系在一起, 因为具备一些很好的语言特性, 以及丰富的框架, 在企业应用中最被青睐, 你总可以听到关于J2EE,JSP,Hi

  • c++使用正则表达式提取关键字的方法

    下面看下c++通过正则表达式提取关键字,代码如下所示: string text = "岳云鹏的对象叫铁锤"; regex pattern("(.*)的对象叫(.*)"); smatch results; if (regex_match(text, results, pattern)) { for (auto it = results.begin(); it != results.end(); ++it) cout << *it << endl

  • C++模拟键盘按键的实例

    这个与模拟鼠标点击的函数差不多,直接上函数 keybd_event(VK_RETURN,0,0,0); keybd_event(VK_RETURN,0,KEYEVENTF_KEYUP,0); 这是模拟按下.抬起回车键 我直接上一个我曾经用它与一些函数写的一个刷屏程序 我用自己的小号试过,如果对方用的是手机,效果很显著 #include<iostream> #include<windows.h> using namespace std; int b[11000],top=0; cha

  • C++实现产生随机数和相应的猜拳小游戏实例代码

    C++实现产生随机数和相应的猜拳小游戏实例代码

    一.简介 c++中,产生随机数的通用方法就是调用 srand()和 rand()  函数. Rand 单纯的rand()会返回一个0至RAND_MAX之间的随机数值,而RAND_MAX的值与int位数有关,最小是32767.不过rand()是一次性的,因为系统默认的随机数种子为1,只要随机数种子不变,其生成的随机数序列就不会改变. 其实,对于rand()的范围,我们是可以进行人为设定的,只需要在宏定义中定义一个random(int x)函数,就可以生成范围为0至x的随机数值.当然,也可以定义为r

  • C++使用异或运算实现交换两个数的值

    异或交换两个数的值是资源开销最小的方法,不需要中介数,原理简单的来说就是异或的负负得正 代码: #include <stdio.h> int main() { int a = 11, b = 22; printf("a=%d b=%d\n", a, b); a = a ^ b; b = a ^ b; a = a ^ b; printf("a=%d b=%d\n", a, b); } 编译: gcc test.c -o test 执行: a=11 b=22

  • 解决C++全局变量只能初始化不能赋值的问题

    C++中,全局变量只能声明.初始化,而不能赋值 也就是说,下面这样是不被允许的: #include <cstdio> using namespace std; int a; a = 2; int main() { return 0; } 错误提示是: C++ requires a type specifier for all declarations 声明.初始化与赋值的区别: 声明:int a; 初始化:int a = 2;(在声明的时候顺带赋值叫做初始化) 赋值:a = 2; 只有定义(i

  • Visual Studio Code配置C、C++环境并编写运行的方法

    弄了半天,总算弄好了,结合网上的教程,整理分享一下~ 总体流程: 下载安装vscode 安装cpptools插件 安装编译.调试环境 修改vscode调试配置文件 下载安装vscode  https://code.visualstudio.com/Download Visual Studio Code 64位 v1.26.0 官方最新安装版:https://www.jb51.net/softs/606746.html Visual Studio Code 32位 v1.26.0 官方最新安装版:

  • C++ 实现球迷 今日头条面试题

    试题描述: 一个球场C的球迷看台可容纳M*N个球迷.官方想统计一共有多少球迷群体,最大的球迷群体有多少人. 球迷选座特性:同球迷群体会选择相邻座位,不同球迷群体选择不相邻的座位.(相邻包括前后相邻.左右相邻.斜对角相邻): 给定一个M*N的二维球场,0代表该位置没人,1代表该位置有人,希望输出球队群体个数P,最大的球队群体人数Q. 输入: 第一行,2个数字,M.N,使用英文逗号隔开. 接下来M行,每行N个数字,使用英文逗号隔开. 输出: 一行,2数字,P和Q. 输入样例: 10,10 0,0,0

  • C++数字三角形问题与dp算法

    题目:数字三角形 题目介绍:如图所示的数字三角形,要求从最上方顶点开始一步一步下到最底层,每一步必须下一层,求出所经过的数字的最大和. 输入:第一行值n,代表n行数值:后面的n行数据代表每一行的数字. 输出:经过数字的最大和. 例: 输入: 4 1 3 2 4 10 1 4 3 2 20 输出: 24 分析:这也是一个典型的贪心算法无法解决的问题,同样可以用动态规划(dp算法)来解决.把边界数字首先初始化到结果矩阵中,再根据状态方程完成结果矩阵的遍历.需要注意的就是数组不是矩形而是三角形,与传统

  • C语言动态规划点杀dp算法LeetCode炒股习题案例解析

    C语言动态规划点杀dp算法LeetCode炒股习题案例解析

    目录 概念 性质 典型特征 实战论证 算法实现 优化 概念 说到动态规划,什么是动态规划? 动态规划(英语:Dynamic programming,简称 dp)通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法.动态规划常常适用于有重叠子问题和最优子结构性质的问题. 看着这么复杂哈,其实总结出来就是大事化小,拆分成小问题但是这些小问题和原问题是同质的,动规致力于解决每一个子问题,减少计算,其实和递归思想,分治法有些类似,斐波那契数列就可以看做入门级的经典动规问题 这里引用一个网上流行的例

  • JavaScript黑洞数字之运算路线查找算法(递归算法)实例

    JavaScript黑洞数字之运算路线查找算法(递归算法)实例

    本文实例讲述了JavaScript黑洞数字之运算路线查找算法.分享给大家供大家参考,具体如下: 运行效果截图如下: 具体代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/19

  • Java实现输出数字三角形实例代码

    Java实现输出数字三角形实例代码

    目录 题目: 题解: 代码: 总结 题目: 给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输入格式 第一行包含整数 nn,表示数字三角形的层数. 接下来 nn 行,每行包含若干整数,其中第 ii 行表示数字三角形第 ii 层包含的整数. 输出格式 输出一个整数,表示最大的路径数字和. 数据范围 1≤n≤5001≤n≤50

  • Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

    Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

    第一部分 问题描述 1.1 具体任务 本次作业任务是轨迹压缩,给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,所有记录的经纬度坐标构成一条轨迹,要求采用合适的压缩算法,使得压缩后轨迹的距离误差小于30m. 1.2 程序输入 本程序输入是一个GPS数据记录文件. 1.3 数据输出 输出形式是文件,包括三部分,压缩后点的ID序列及坐标.点的个数.平均距离误差.压缩率 第二部分 问题解答 根据问题描述,我们对问题进行求解,问题求解分为以下几步: 2.1 数据预处理 本次程序输入为GPS

  • Python实现曲线点抽稀算法的示例

    Python实现曲线点抽稀算法的示例

    本文介绍了Python实现曲线点抽稀算法的示例,分享给大家,具体如下: 目录 何为抽稀 道格拉斯-普克(Douglas-Peuker)算法 垂距限值法 最后 正文 何为抽稀 在处理矢量化数据时,记录中往往会有很多重复数据,对进一步数据处理带来诸多不便.多余的数据一方面浪费了较多的存储空间,另一方面造成所要表达的图形不光滑或不符合标准.因此要通过某种规则,在保证矢量曲线形状不变的情况下, 最大限度地减少数据点个数,这个过程称为抽稀. 通俗的讲就是对曲线进行采样简化,即在曲线上取有限个点,将其变为折

  • C语言深入探究动态规划之线性DP

    C语言深入探究动态规划之线性DP

    目录 写在前面 数字三角形 最长上升子序列 最长上升子序列 II 最长公共子序列 写在前面 之前讲过背包问题,不知道大家忘了吗,如果忘了可以点这里,这次是线性DP 数字三角形 状态表示:f[i,j],到点i,j的最大路径 状态计算:f[i,j] = MAX(f[i-1,j-1]+a[i,j],f[i-1,j]+a[i,j]) 看图,以例题为例,将它看成五行五列的三角形,每个点都可以用坐标表示.那么我们可以得知到一个数的最大路径要么来自左上,要么来自右上.左上的数用f[i-1,j-1]表示,右上的

  • python数据结构leetcode338比特位计数算法

    目录 一.题目内容 示例 1: 示例 2: 进阶: 二.解题思路 三.代码 一.题目内容 给定一个非负整数 num.对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回. 示例 1: 输入: 2 输出: [0,1,1] 示例 2: 输入: 5 输出: [0,1,1,2,1,2] 进阶: 给出时间复杂度为O(n*sizeof(integer))的解答非常容易.但你可以在线性时间O(n)内用一趟扫描做到吗? 要求算法的空间复杂度为O(n). 你能进

  • Luhn算法学习及其Ruby版实现代码示例

    关于LUHN算法 LUHN算法,主要用来计算信用卡等证件号码的合法性. 1.从卡号最后一位数字开始,偶数位乘以2,如果乘以2的结果是两位数,将两个位上数字相加保存. 2.把所有数字相加,得到总和. 3.如果信用卡号码是合法的,总和可以被10整除. Luhn 算法或是Luhn 公式,也被称作"模10算法".它是一种简单的校验公式,一般会被用于身份证号码,IMEI号码,美国供应商识别号码,或是加拿大的社会保险号码的验证.该算法是由IBM的科学家Hans Peter Luhn所创造,于195

  • JavaScript累加、迭代、穷举、递归等常用算法实例小结

    本文实例讲述了JavaScript迭代.迭代.穷举.递归等常用算法.分享给大家供大家参考,具体如下: 累加和累积 累加:将一系列的数据加到一个变量里面.最后的得到累加的结果 比如:将1到100的数求累加和 小球从高处落下,每次返回到原来一半,求第十次小球落地时小球走过的路程 <script> var h=100; var s=0; for(var i=0;i<10;i++){ h=h/2; s+=h; } s=s*2+100; </script> 累积:将一系列的数据乘积到一

随机推荐