AcWing898. 数字三角形

线性DP
在这里插入图片描述

董晓老师的讲解是从下标0开始算的,其实我们从1开始也可以,我感觉这里从1开始更好理解。是从下往上计算的。j负责列的计算,往上计算时逐步收窄横向的范围,i是纵向的从下往上算,
下面是内存布局
在这里插入图片描述
下面是逻辑上的布局
在这里插入图片描述
下面的代码是优化之后的代码,正常来说是f数组存储总和sum,w数组是存储输入的数字,然后f初始值是0的,每次加上w里面的数,
f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] + w [ i ] [ j ] , f [ i + 1 ] [ j + 1 ] + w [ i ] [ j ] ) f[i][j] = max(f[i+1][j] + w[i][j] ,f[i+1][j+1] + w[i][j] ) f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j])
优化为
f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] , f [ i + 1 ] [ j + 1 ] ) + w [ i ] [ j ] f[i][j] = max(f[i+1][j] ,f[i+1][j+1] ) + w[i][j] f[i][j]=max(f[i+1][j],f[i+1][j+1])+w[i][j]
然后发现w数组和f数组作用雷同,直接用f存储输入的三角形,然后累加的时候覆盖上面的值就完事儿了
就直接优化为
f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] , f [ i + 1 ] [ j + 1 ] ) + f [ i ] [ j ] f[i][j] = max(f[i+1][j],f[i+1][j+1]) + f[i][j] f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j] ;.
等价于
f [ i ] [ j ] + = m a x ( f [ i + 1 ] [ j ] , f [ i + 1 ] [ j + 1 ] ) f[i][j] += max(f[i+1][j],f[i+1][j+1]) f[i][j]+=max(f[i+1][j],f[i+1][j+1]);

#include<iostream>
#include<algorithm>
#define N 510
using namespace std;
int n;
int f[N][N];
int main(){cin >> n ;for(int i = 1;i <= n; ++i){for(int j = 1; j <= i; ++j){cin >> f[i][j];}}for(int i = n - 1;i >= 1; --i){for( int j = 1 ; j <= i ; ++j){f[i][j] += max(f[i+1][j],f[i+1][j+1]);}}cout << f[1][1];return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/412658.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

android 离线的方式使用下载到本地的gradle

1、android studio在下载gradle的时候&#xff0c;特别慢&#xff0c;有的时候会下载不完的情况&#xff0c;这样我们就要离线使用了。 2、下载Gradle Gradle | Releases 或者 Releases gradle/gradle GitHub Gradle | Releases 这里我们下载8.10 complete版本&#xff0c…

Tomcat10安装

Tomcat下载 进入官网下载https://tomcat.apache.org 注意tomcat版本和Java版本的对应关系&#xff1a; 配置好JAVA_HOME 安装tomcat前&#xff0c;需要先配置好JAVA_HOME&#xff0c;因为tomcat启动时候默认会找环境里面的JAVA_HOME&#xff0c;这里选择的Java版本是java1…

【工具篇】高效记忆方法之AnKi工具

&#x1f60a;你好&#xff0c;我是南极。正在变强的路上不断地努力着&#x1f4aa; &#x1f514;今天和大家分享一些记忆的方法&#xff0c;以及推荐了一款用于复习和巩固知识的软件AnKi。 对我们程序员而言&#xff0c;平常学习的东西会比较多&#xff0c;有时呢学的东西会…

结合代码详细讲解DDPM的训练和采样过程

本篇文章结合代码讲解Denoising Diffusion Probabilistic Models&#xff08;DDPM&#xff09;&#xff0c;首先我们先不关注推导过程&#xff0c;而是结合代码来看一下训练和推理过程是如何实现的&#xff0c;推导过程会在别的文章中讲解&#xff1b;首先我们来看一下论文中的…

<C++> AVLTree

目录 1. AVL概念 2. AVL树节点的定义 3. AVL树的插入 4. AVL树的旋转 5. AVL树的验证 6. AVL树的删除 7. AVL树的性能 暴力搜索、二分搜索、二叉搜索树、二叉平衡搜索树&#xff08;AVL、红黑树&#xff09;、多叉平衡搜索树&#xff08;B树&#xff09;、哈希表 1. AVL概念 二…

【C++ Primer Plus习题】7.2

问题: 解答: #include <iostream> using namespace std;#define MAX 10int input(float* grade, int len) {int i 0;for (i 0; i < len; i){cout << "请输入第" << i 1 << "个高尔夫成绩(按0结束):";cin >> grade[i]…

更改了ip地址怎么改回来

在日常的网络使用中&#xff0c;‌我们有时会因为特定的需求更改设备的IP地址&#xff0c;‌比如解决IP冲突、‌访问特定网络资源或进行网络测试等。‌然而&#xff0c;‌更改IP地址后&#xff0c;‌我们可能又因为某些原因需要将IP地址改回原来的设置。‌本文将详细介绍如何改…

视频号单场直播GMV超500万!开学季助力品牌高效转化

开学在即&#xff0c;友望数据发现&#xff0c;不少学习机、学练机、智能机器人、词典笔等学习相关的电子教育产品开始畅销 ▲ 图片来源&#xff1a;友望数据-商品排行榜 新学年开始&#xff0c;家长们又要为孩子新的学业操碎心&#xff0c;而教育培训商家也在开学季迎来了他们…

PS如何抠人像图--5步实现完美抠图

1、菜单栏--选择--选择主体 2、菜单栏--选择--选择并遮住 3、选择原图--右下角添加纯色背景 4、文件--导出--导出为png图片 5、原图与抠图效果对比 相关参考视频&#xff1a; 【ps教程】揭秘PS抠头发&#xff0c;这才是真正的教学&#xff0c;快收藏吧_哔哩哔哩_bilibili 一分…

挂载5T大容量外接硬盘到ubuntu

挂载5T大容量外接硬盘到ubuntu S1&#xff1a;查看硬盘 使用 $ sudo fdisk -l找到对应盘&#xff0c;例如下图所示 /dev/sdc S2: 创建分区 使用 $ sudo fdisk /dev/sdc对上硬盘进行创建分区&#xff1b;可以依次使用以下指令 m &#xff1a;查看命令&#xff1b; g &…

从开题到答辩:ChatGPT超全提示词分享!(下)【建议收藏】

数据收集 1. "请帮我找出关于如何收集【研究领域】社交媒体数据进行消费者行为研究的五篇指导性文章&#xff0c;并概述它们的主要方法论摘要。" 2. "我需要对【特定领域】市场的消费者偏好进行调查。能否提供一份包含调查问卷设计原则和示例的草稿&#xff1f;…

cola_os学习笔记(下)

cola_os学习笔记&#xff08;上&#xff09; os文件夹 cola_device.c ​ .h放在.c的同层级。作者采用了字符设备注册的方式&#xff0c;在.h中可以看到设备属性。也就是把LED这些设备抽象&#xff0c;外面传入"LED1"这样的参数&#xff0c;使我联想到java的new一个…

编译错误cc:not found总结

一、错误 cc: not found 系统无法找到名为cc的编译器。 注&#xff1a;在大多数Linux系统中&#xff0c;cc通常是C编译器的链接&#xff08;link&#xff09;或别名&#xff0c;它通常指向gcc&#xff08;GNU Compiler Collection&#xff09;或其他C编译器。 二、可能导致…

「OC」CAlayer——巧用动画实现一个丝滑的折叠cell

「OC」CAlayer——巧用动画实现一个丝滑的折叠cell 前言 在这个暑假集训后的时间&#xff0c;都在家里做着学习笔记的整理&#xff0c;深入学习了CALayer的相关知识&#xff0c;掌握了第三方库Masonry自动布局的用法&#xff0c;以及学习了MVC的相关内容&#xff0c;正好组内…

chapter08-面向对象编程——(Object类详解)——day09

目录 319-运算符 320-查看Jdk源码 321-子类重写equals 322-equals课堂练习1 323-equals重写练习2 324-equals重写练习3 325-hashCode 326-toString 327-finalize 319-运算符 引用的都是同一个地址&#xff0c;所以返回true 320-查看Jdk源码 equals只能判断引用类型是…

艾体宝干货丨Redis与MongoDB的区别

Redis&#xff08;Remote Dictionary Server&#xff0c;远程字典服务器&#xff09;和 MongoDB 是两类知名的 NoSQL数据库&#xff0c;其以非结构化的方式存储数据。与传统关系数据库使用表格、行和列来组织数据不同&#xff0c;NoSQL数据库采用了不同的数据存储模型。Redis是…

探索极速Python:Sanic框架的魔力

文章目录 探索极速Python&#xff1a;Sanic框架的魔力背景&#xff1a;为什么选择Sanic&#xff1f;Sanic是什么&#xff1f;如何安装Sanic&#xff1f;简单的库函数使用方法场景应用示例常见Bug及解决方案总结 探索极速Python&#xff1a;Sanic框架的魔力 背景&#xff1a;为什…

【位置编码】【Positional Encoding】直观理解位置编码!把位置编码想象成秒针!

【位置编码】【Positional Encoding】直观理解位置编码&#xff01;把位置编码想象成秒针&#xff01; 你们有没有好奇过为啥位置编码非得长成这样&#xff1a; P E ( p o s , 2 i ) s i n ( p o s 1000 0 2 i / d m o d e l ) P E ( p o s , 2 i 1 ) c o s ( p o s 1000 …

AcWing895. 最长上升子序列

这个代码不知道怎么说&#xff0c;反正就是对着代码手算一次就懂了&#xff0c;无需多言&#xff0c;就是俩for循环里面的第二层for的循环条件是j<i,j是从下标1往下标i-1遍历的&#xff0c;每次a【j】<a【i】就在答案数组f【i】上面做出更新。基本的输入样例已经可以覆盖…

红黑树刨析(删除部分)

文章目录 红黑树删除节点情景分析情景1&#xff1a;删除节点左右子树都为空情景1.1&#xff1a;删除节点为红色情景1.2&#xff1a;删除节点为黑色情况1.2.1&#xff1a;删除节点的兄弟节点是红色情景1.2.2&#xff1a;删除节点的兄弟节点是黑色情景1.2.2.1&#xff1a;删除节点…