C++笔试练习笔记【5】:最小花费爬楼梯(有题目链接) 初识动态规划

文章目录

  • 题目
    • 思路
    • 代码
  • 动态规划简介
    • **一、什么是动态规划**
    • **二、动态规划的应用场景**
    • **三、动态规划的基本步骤**
    • **四、动态规划的优缺点**

题目

题目链接:https://www.nowcoder.com/practice/9b969a3ec20149e3b870b256ad40844e?tpld=230&tpld=39751&ru=/exam/oj

在这里插入图片描述

思路

有几个细节要明确
在这里插入图片描述

  • const[i]是在离开时花费的体力所以在离开时才会加
  • 根据例子我们能知道数组给了i个数我们下标到达i才算到顶,如图如果我们必须到达cost[i+1]才算登顶

动态规划:

  1. 状态表示:
    dp[i]:到达i位置所用最小花费
  2. 状态转移方程
    在这里插入图片描述
    因为一次只能向上一个台阶或者两个台阶所以只有i-1,i-2两种可能。
	dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

代码

#include <iostream>
using namespace std;#define N 100010int main() {int cost[N]={0};int dp[N]={0};int n;cin >> n;for(int i=0;i<n;i++)cin >> cost[i];for(int i=2;i<=n;i++)dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);cout << dp[n] << endl;return 0;
}

动态规划简介

一、什么是动态规划

动态规划(Dynamic Programming)是一种在解决多阶段决策问题时常用的算法思想。它通过将复杂问题分解成一系列相互关联的子问题,并按照一定的顺序求解这些子问题,从而避免了重复计算,提高了算法的效率。上面的题的思想就是动态规划。

动态规划的核心思想是“最优子结构”和“重叠子问题”。最优子结构意味着一个问题的最优解包含了其子问题的最优解。重叠子问题则是指在求解过程中,相同的子问题会被多次计算。

二、动态规划的应用场景

动态规划在许多领域都有广泛的应用,例如:

  1. 求解最短路问题,如在图中找到从一个节点到另一个节点的最短路径。
    • 例如,在一个城市交通网络中,寻找从起点到终点的最短行驶路线。
  2. 资源分配问题,如何合理分配有限的资源以达到最优效果。
    • 比如在项目管理中,合理分配人力和时间资源,以使项目能够在最短时间内完成。
  3. 背包问题,给定一组物品和一个背包容量,选择哪些物品放入背包能使价值最大化。

三、动态规划的基本步骤

  1. 定义状态表示:明确问题中的状态变量,这些变量通常用来描述子问题的解。
  2. 建立状态转移方程:找出不同状态之间的关系,确定如何从一个状态转移到另一个状态。
  3. 初始化边界条件:确定初始状态的值。
  4. 按照合适的顺序计算状态值:通常是从边界条件开始,逐步计算其他状态的值。

四、动态规划的优缺点

优点:

  1. 能够有效地降低算法的时间复杂度,避免重复计算。
  2. 对于具有最优子结构和重叠子问题的问题,能够得到最优解。

缺点:

  1. 空间复杂度可能较高,需要存储状态值。
  2. 状态定义和转移方程的推导可能比较困难,需要对问题有深入的理解。

总之,动态规划是一种强大的算法思想,掌握它对于解决许多复杂的优化问题具有重要意义。但在实际应用中,需要根据具体问题的特点来选择是否使用动态规划以及如何设计有效的算法。

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

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

相关文章

IT课程学习搭子

各种IT课程齐全可学&#xff0c;价格你绝对想不到&#xff0c;相比于培训班有以下优势&#xff1a; 1、避免被割韭菜&#xff0c;避免踩坑&#xff0c;避免交智商税&#xff0c;最低的成本学最有价值的课&#xff0c;同时又能达到比培训班更好的效果 2、收徒&#xff0c;带你学…

【Linux课程学习】:对于权限的理解(粘滞位)

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;Linux课程学习 &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 这篇文章主要理解权限的概念&#xff0c;以及如何更改…

KubeVirt虚拟机存储及网络卸载加速解决方案

1. 方案背景 1.1. KubeVirt介绍 随着云计算和容器技术的飞速发展&#xff0c;Kubernetes已成为业界公认的容器编排标准&#xff0c;为用户提供了强大、灵活且可扩展的平台来部署和管理各类应用。然而&#xff0c;在企业的实际应用中&#xff0c;仍有许多传统应用或遗留系统难…

AOP学习

AOP概述 AOP&#xff08;Aspect Oriented Programming&#xff09;&#xff1a;⾯向切⾯编程&#xff0c;它是⼀种思想&#xff0c;它是对某⼀类事情的集中处理。 什么是SpringAOP? ⽽ AOP 是⼀种思想&#xff0c;⽽ Spring AOP 是⼀个框架&#xff0c;提供了⼀种对 AOP 思…

【Vue3】element-plus中el-tree的递归处理赋值回显问题

由于项目是从0-1开始构建的rbac都需要重新构建对接 所以涉及到了权限管理和菜单管理 整体思路很简单&#xff1a;初始化树 -> 处理 el-tree 回显 -> 递归处理所有层级菜单选中的id 不处理情况下&#xff1a; 只要勾选一个子节点&#xff0c;回来接收到的父节点数据 会…

Java面试题——第三篇(JVM)

1. 什么情况下会发生栈内存溢出 栈是线程私有的&#xff0c;他的生命周期和线程相同&#xff0c;每个方法在执行的时候都会创建一个栈帧&#xff0c;用来存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程&#xff0c;就对应着一个栈帧…

剪映怎么剪辑视频?2024年视频剪辑新手必读指南!

在快节奏的工作里&#xff0c;掌握快速剪辑视频的技巧真的很有用。不管是要做个产品展示、录制培训材料&#xff0c;还是制作社交媒体上的内容&#xff0c;有一款好用的视频剪辑软件&#xff0c;工作效率立马提升好几个档次。咱们今天就先来聊聊剪映怎么剪辑视频&#xff1f;如…

如果忘了Linux密码如何重置?

忘记密码是我们常会遇到的情况之一&#xff0c;无论是在操作系统、网站账户、手机、电子邮件还是其他渠道上。 忘记密码是我们常会遇到的情况之一&#xff0c;无论是在操作系统、网站账户、手机、电子邮件还是其他渠道上。有时候如果密码需要符合特定的复杂性要求&#xff0c;…

哈佛大学单细胞课程|笔记汇总 (三)

哈佛大学单细胞课程|笔记汇总 &#xff08;一&#xff09; 哈佛大学单细胞课程|笔记汇总 &#xff08;二&#xff09; 听哈佛大神讲怎么做单细胞转录组GSEA分析 &#xff08;三&#xff09;Single-cell RNA-seq: Quality control set-up 在生成count矩阵后&#xff0c;我们需…

基于大数据的混合音乐推荐系统的设计与设计(论文+源码)_kaic

摘 要 随着数据的不断增长和用户对随听随播的收听方式的习惯&#xff0c;开发一款音乐推荐系统变得越来越必要。为了满足这一需求&#xff0c;本论文采用Java语言、Vue以及数据库MySQL进行开发。系统的主要功能包括登录注册、音乐分类管理、音乐推荐管理、音乐资讯管理、音乐库…

PCIe学习笔记(16)

层次结构&#xff08;Hierarchy&#xff09;ID Message &#xff08;PCIe I/O 互连的树形拓扑结构称为 PCIe 的 Hierarchy&#xff0c;或称层级、层次&#xff08;不是事务层、数据链路层的“层”&#xff09;。层次区域是指与 RC 某一 RP 相关联的所有设备和链路组成的线路结…

微服务之SpringAMQP详解

目录 前言 1. 概述 2. Basic Queue简单队列模型 2.1 消息发送 2.2 消息接收 2.3 总结 3. WorkQueue模型 3.1 消息发送 3.2 消息接收 3.3 测试 3.4 消费预取限制 3.5 总结 4. 发布、订阅 5. Fanout 5.1 声明队列和交换机 5.2 消息发送 5.3 消息接收 5.4 测试 5…

Linux常用命令学习

常用apt命令. apt&#xff08;Advanced Packaging Tool&#xff09;是一个在 Debian 和 Ubuntu 中的 Shell 前端软件包管理器。 apt 命令提供了查找、安装、升级、删除某一个、一组甚至全部软件包的命令&#xff0c;而且命令简洁而又好记。 apt 命令执行需要超级管理员权限(ro…

【Java】Java泛型、集合、UML统一建模语言、final关键字

昨天在昆仑巢&#xff0c;下午练习Spring Boot的过滤器Filter。 昨天傍晚开始阅读《疯狂Java讲义(第2版)》&#xff0c;熟悉了UML建模语言、Final修饰符、List集合和泛型。 1.UML建模语言: 13种图&#xff0c;常用的包括用例图、类图、组件图、部署图、顺序图、活动图和状态机…

JVM结构、架构与生命周期总结

【1】JVM结构 不同厂商的JVM产品 &#xff1a; 厂商JVMOracle-SUNHotspotOracleJRocketIBMJ9 JVM阿里Taobao JVM HotSpot VM是目前市面上高性能虚拟机的代表作之一。它采用解释器与即时编译器并存的架构。 在今天&#xff0c;Java程序的运行性能早已脱胎换骨&#xff0c;已…

文章管理接口——里面有动态SQL编写,在分页查询里

1.实体类和表结构 2. 新增文章分类 接口文档 实现 完整代码放在校验部分 结果&#xff1a; 参数校验&#xff08;Validation自定义&#xff09; 对state的校验&#xff08;已发布|草稿&#xff09;&#xff0c;已有的注解不能满足校验需求&#xff0c;这时就需要自定义校验注解…

[Bugku] web-CTF靶场系列系列详解④!!!

平台为“山东安信安全技术有限公司”自研CTF/AWD一体化平台&#xff0c;部分赛题采用动态FLAG形式&#xff0c;避免直接抄袭答案。 平台有题库、赛事预告、工具库、Writeup库等模块。 --------------------------------- eval 开启环境&#xff1a; 进入页面发现是一道php题&…

如何用 ChatGPT 提升学术写作:15 个高效提示

在本文&#xff0c;我们详细探讨了如何利用 ChatGPT 提升学术写作的各个方面。我们帮助学术作者通过生成创意点子、构建论证结构、克服写作障碍以及格式化引用&#xff0c;从而显著提升其学术论文的质量。这 15 条提示不仅可以单独使用&#xff0c;还可作为学习的良好范例。 本…

集合基础知识及练习

import java.util.ArrayList;public class Solution {//将字符串转化为整数public static void main(String[] args) {ArrayList<String> listnew ArrayList();list.add("aaa");list.add("aaa");list.add("bbb");list.add("ccc"…

Occlusion in Augmented Reality

1.Occlusion in Augmented Reality 笔记来源&#xff1a; 1.Occlusion handling in Augmented Reality context 2.Occlusion in Augmented Reality 3.Real-Time Occlusion Handling in Augmented Reality Based on an Object Tracking Approach 4.Occlusion Matting: Realisti…