动态规划理论基础和习题【力扣】【算法学习day.22】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!


理论基础

动态规划和贪心的区别在于,贪心是以局部最优推出全局最优,只需做到局部最优即可。而动态规划的局部受上一步的影响。举个例子:

贪心:背包容量5,石头大小分别为:1,2,3,4,问怎么拿可以取更多个石头

动态规划:背包容量5,石头大小分别为:1,2,3,4,价值分别为:1,2,1000,3,问怎么拿价值最大

对于贪心,就是假设有一个数组,每次从数组中拿最小的即可,这样就能尽可能多拿石头,且每一步并没有对结果有所影响。

对于动态规划,如果前两次我取了1,2,那么就不能取3,而3的价值很高,可见,前面的选择会影响后面的选择。


习题

1.斐波那契数

题目链接:509. 斐波那契数 - 力扣(LeetCode)

题面:

基本分析:从n=2开始,等于前两个数之和

代码: 

class Solution {public int fib(int n) {int a = 0;int b = 1;int ans = 0;if(n==0)return a;else if(n==1)return b;for(int i = 2;i<=n;i++){ans= a+b;a=b;b=ans;}return ans;}
}

2.爬楼梯

题目链接:70. 爬楼梯 - 力扣(LeetCode)

题面:

基本分析:到第n个楼梯的爬法等于n-1的爬法+n-2的爬法

代码:

class Solution {public int climbStairs(int n) {int a=1,b=1,sum=1;for(int i = 2;i<=n;i++){sum=0;sum+=a;sum+=b;a=b;b=sum;}return sum;}}

3.使用最小花费爬楼梯

题目链接:746. 使用最小花费爬楼梯 - 力扣(LeetCode)

题面:

代码:

class Solution {public int minCostClimbingStairs(int[] cost) {int size = cost.length;int[] minCost = new int[size];minCost[0] = 0;minCost[1] = Math.min(cost[0], cost[1]);for (int i = 2; i < size; i++) {minCost[i] = Math.min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);}return minCost[size - 1];}
}

4.不同路径

题目链接:62. 不同路径 - 力扣(LeetCode)

题面:

代码:

class Solution {public int uniquePaths(int m, int n) {int[][] f = new int[m][n];f[0][0] = 1;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i > 0 && j > 0) {f[i][j] = f[i - 1][j] + f[i][j - 1];} else if (i > 0) {f[i][j] = f[i - 1][j];} else if (j > 0) {f[i][j] = f[i][j - 1];}}}return f[m - 1][n - 1];}
}

后言

上面是动态规划的基本概念和部分习题,下一篇会有其他习题,希望有所帮助,一同进步,共勉!   

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

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

相关文章

HTTP、WebSocket、gRPC 或 WebRTC:各种协议的区别

在为您的应用程序选择通信协议时&#xff0c;有很多不同的选择。 本文将了解四种流行的解决方案&#xff1a;HTTP、WebSocket、gRPC 和 WebRTC。 我们将通过深入学习其背后原理、最佳用途及其优缺点来探索每个协议。 通信方式在不断改进&#xff1a;变得更快、更方便、更可靠&…

大模型微调技术 --> LoRA 系列之 QLoRA (省资源能手)

QLoRA 1.摘要 作者提出了QLoRA&#xff0c;一种有效的微调方法&#xff0c;可以减少内存使用&#xff0c;足以在单个48 GB GPU上微调 65B 参数模型&#xff0c;同时保留完整的 16位 微调任务性能。 QLoRA 通过冻结的4位量化预训练语言模型将梯度反向传播到低秩适配器&#x…

一种ESB的设计

系统架构 ESB包括&#xff1a; ESB总控服务、业务应用集群、业务消息WEB服务、业务消息日志服务、运维管理平台、业务设计器。如下图所示 ESB总控服务 ESB总控服务承载了各项业务的运维和管理。主要包括&#xff1a; 业务流程的管理ESB内部不同模块间的通讯ESB系统设置和管理…

06 网络编程基础

目录 1.通信三要素 1. IP地址&#xff08;Internet Protocol Address&#xff09; 2. 端口号&#xff08;Port Number&#xff09; 3. 协议&#xff08;Protocol&#xff09; 2.TCP与UDP协议 三次握手&#xff08;Three-Way Handshake&#xff09; 四次挥手&#xff08;…

使用sealos部署的集群在部署metrics-server时日志x509

1、下载文件并进行部署 wget https://github.com/kubernetes-sigs/metrics-server/releases/latest/download/components.yaml2、进行部署 kubectl apply -f components.yaml3、发现问题 pod容器已经启动但是健康检查没有通过 kubectl get pod -n kube-system metrics-server…

定海 - 利用Coraza引擎开发一个防火墙

1. 介绍: Coraza有大量的内置安全规则,包括 OWASP Top 10&#xff0c;同时将错误警报降至最低。CRS保护免受许多常见攻击类别的攻击&#xff0c;包括SQL注入&#xff08;SQLi&#xff09;、跨站点脚本&#xff08;XSS&#xff09;、PHP和Java代码注入、HTTPoxy、Shellshock、脚…

【Linux】冯诺依曼体系、再谈操作系统

目录 一、冯诺依曼体系结构&#xff1a; 1、产生&#xff1a; 2、介绍&#xff1a; 二、再谈操作系统&#xff1a; 1、为什么要管理软硬件资源&#xff1a; 2、操作系统如何进行管理&#xff1a; 3、库函数&#xff1a; 4、学习操作系统的意义&#xff1a; 一、冯诺依曼…

bat批量处理脚本细节研究

文章目录 bat批处理脚本&#xff08;框架&#xff09;set变量设置基本语法显示环境变量 自定义环境变量临时环境变量和永久环境变量特殊环境变量和系统默认环境变量set命令利用选项的其他应用 !与%解析变量的区别/为什么使用setlocal enabledelayedexpansion区别%的规则!使用 %…

ReactPress系列—Next.js 的动态路由使用介绍

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress 欢迎提出宝贵的建议&#xff0c;感谢Star。 Next.js 的动态路由使用介绍 Next.js 是一个流行的 React 框架&#xff0c;支持服务端渲染、静态站点生成和动态路由等功能&#xff0c;极大地简化…

计算机的发展史

计算机的发展史是一个跨越多个世纪的过程&#xff0c;从最早的机械计算设备到如今的高性能、智能化计算机。以下是计算机发展史的简要概述&#xff0c;按重要的技术进步和里程碑进行归类&#xff1a; 1. 早期的计算工具&#xff08;公元前3000年—17世纪&#xff09; 计算机的…

基于STM32的实时时钟(RTC)教学

引言 实时时钟&#xff08;RTC&#xff09;是微控制器中的一种重要功能&#xff0c;能够持续跟踪当前时间和日期。在许多应用中&#xff0c;RTC用于记录时间戳、定时操作等。本文将指导您如何使用STM32开发板实现RTC功能&#xff0c;通过示例代码实现当前时间的读取和显示。 环…

Python | Leetcode Python题解之第537题复数乘法

题目&#xff1a; 题解&#xff1a; class Solution:def complexNumberMultiply(self, num1: str, num2: str) -> str:real1, imag1 map(int, num1[:-1].split())real2, imag2 map(int, num2[:-1].split())return f{real1 * real2 - imag1 * imag2}{real1 * imag2 imag1…

CoD-MIL: 基于诊断链提示的多实例学习用于全切片图像分类|文献速递-基于深度学习的病灶分割与数据超分辨率

Title 题目 CoD-MIL: Chain-of-Diagnosis Prompting Multiple Instance Learning for Whole Slide Image Classification CoD-MIL: 基于诊断链提示的多实例学习用于全切片图像分类 01 文献速递介绍 病理检查被广泛视为肿瘤诊断的金标准&#xff0c;因为它为治疗决策和患者…

232转485模块测试

概述 常用的PLC一般会有两个左右的232口&#xff0c;以及两个左右的485口&#xff0c;CAN口等&#xff0c;但是PLC一般控制的设备可能会有很多&#xff0c;会超出通讯口的数量&#xff0c;此时我们一般会采用一个口接多个设备&#xff0c;这种情况下要注意干扰等因素&#xff0…

网络编程——TCP通信练习

目录 一、多发多收 二、接收和反馈 三、上传文件 四、解决上传文件名重复问题 五、上传文件多线程版 六、上传文件线程池版 七、B/S(接收浏览器的消息并打印) 一、多发多收 客户端&#xff1a;多次发送数据 服务器&#xff1a;接收多次数据&#xff0c;并打印 public cl…

【stm32】RTC时钟的介绍与使用

RTC时钟的介绍与使用 一、时间戳1、Unix时间戳2、UTC/GMT3、时间戳转换 二、BKP简介及代码编写1、BKP简介2、BKP基本结构3、BKP库函数介绍&#xff1a;4、程序编写&#xff1a; 三、RTC简介及代码编写1、RTC简介2、RTC框图2、RTC基本结构3、RTC相关库函数介绍&#xff1a;4、程…

在docker中搭建redis哨兵环境

文章目录 一、引言二、环境准备前提条件目录结构 三、配置文件1. 主节点配置文件 sentinel-master.conf2. 从节点配置文件3. 哨兵配置文件 sentinel.conf4. Docker Compose 文件 四、启动 Docker Compose五、验证哨兵机制1. 检查主节点状态2. 检查从节点状态3. 检查哨兵状态4. …

职场高手揭秘,细节如何左右你的成败与升迁之路

身在职场&#xff0c;每一个人都想得到老板的器重&#xff0c;能不断地加薪、升职&#xff0c;从而获得职场的成功。但你知道&#xff0c;影响一个人职场成功&#xff0c;或者说影响升职加薪的最重要因素是什么吗&#xff1f; 许多人会说那要靠运气&#xff0c;也有人认为工作…

微信小程序 高校教材征订系统

文章目录 项目介绍具体实现截图技术介绍mvc设计模式小程序框架以及目录结构介绍错误处理和异常处理java类核心代码部分展示详细视频演示源码获取 项目介绍 系统分为三个角色&#xff0c;分别是教材科、系教学秘书、教研室主任。系统主要完成功能是教材科要发布教材征订信息&am…

RNN中的梯度消失与梯度爆炸问题

梯度消失与梯度爆炸问题 循环神经网络&#xff08;Recurrent Neural Network&#xff0c;RNN&#xff09;是一类具有短期记忆能力的神经网络&#xff0e;在循环神经网络中&#xff0c;神经元不但可以接受其他神经元的信息&#xff0c;也可以接受自身的信息&#xff0c;形成具有…