动态规划基础
动态规划
1、动态规划的概念
简称DP,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。
简单来说,就是给定一个问题,把它拆成一个个子问题,查到子问题可以直接解决。然后把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。
核心思想:在于拆分子问题,记住过往,减少重复计算。
2、动态规划的步骤
- 划分子问题
- 状态表示,一般用数组dp[i]表示当前状态
- 状态转移,即当前状态是由前面那些状态转移过来的,例如dp[i]=dp[i-1],表示当前状态可以由上一个状态转移过来
- 确定边界,确定初始状态
一、线性DP
1、线性DP的概念
动态规划中的一类问题,指状态之间有线性关系的动态规划问题。所谓线性DP,就是递推方程是有一个明显的线性关系的,一维线性和二维线性都有可能。在求的时候,一行一行地来求。
例题----取钱
https://www.lanqiao.cn/problems/3297/learning/
黄开的银行最近又发行了一种新面额的钞票面值为4,所以现在黄有5种面额的钞票,分别是20,10,5,4,1。但是不变的是他小气,现在又有很多人来取钱,黄又不开心了,请人来取钱,黄又不开心了,请你算出每个来取钱的人黄应该给他至少多少张钞票。
输入格式:每个测评数据含有不超过10组输入,每组给出一个n(1<=n<=10000),n为要取出的金额。
输出格式:每组样例输出一个答案(钞票数)。
示例:20 1
2 2
6 2
提示:
设置dp[i]数组 取出金额为i
最小钞票数 转移方程为:dp[i]=Math.min(dp[i-1],dp[i-4],dp[i-5],dp[i-10],dp[i-20])+1
import java.util.Arrays;
import java.util.Scanner;public class Main {
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] arr = { 1, 4, 5, 10, 20 };int[] dp = new int[10001]; // 索引为金额, 值为方案数Arrays.fill(dp, 10000);dp[0] = 0; // 0金额的可选方案数量为0个for (int i = 1; i < dp.length; ++i) { // 枚举子问题金额数for (int j : arr) { // 每个子问题可选方案if (i >= j) { // 当金额大于等于面额时dp[i] = Math.min(dp[i - j] + 1, dp[i]); // 选择当前面额后 +1,且寻找剩余金额时方案数累加,与当前j之后的面额继续对比方案数}}}while (sc.hasNext()) {System.out.println(dp[sc.nextInt()]);}}
}
例题---破损的楼梯
https://www.lanqiao.cn/problems/3367/learning/
小蓝来到了一座高耸的楼提前,楼梯共有N级台阶,从第0级台阶出发。小蓝每次可以迈上1级或2级台阶。但是,楼梯上的第级,第级,第级,以此类推,共m级台阶的台阶面已经坏了,不能踩上去。
现在,小蓝想要到达楼梯的顶端,也就是第N级台阶,但他不能踩到坏了的台阶上。请问他有多少种不踩坏了的台阶到达顶端的方案数?由于方案数很大,请输入其对+7取模的结果。
输入格式:
第一行包含两个正整数N(1<=N<=)和M(0<=M<=N),表示楼梯的总级数和坏了的台阶数。
接下来一行,包含M个正整数
相关文章:
动态规划基础
动态规划 1、动态规划的概念 简称DP,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。 简单来说,就是给定一个问题,把它拆成一个个子问题,查到子问题可以直接解决。然后把子问题答案保存起来,以减少重复计算…...
kubeadm部署的k8s1.29集群证书更新
1、查看证书有效期 kubeadm certs check-expiration更新证书前: [check-expiration] Reading configuration from the cluster... [check-expiration] FYI: You can look at this config file with kubectl -n kube-system get cm kubeadm-config -o yamlCERTIFIC…...
【A 类比赛】大学生学科竞赛智慧应用场景题目大全
智能应用的多彩场景:未来生活的无限可能 随着科技的飞速发展,智能应用已经渗透到我们生活的方方面面,它们不仅极大地提高了工作效率,也丰富了我们的生活体验。从家庭到工作场所,从城市到乡村,智能应用正在…...
Yarn的安装和使用(2):使用及问题解决
Yarn是JavaScript的依赖管理工具,它与npm类似,但提供了一些额外的性能优化和一致性保证。 Yarn的使用: 初始化项目: yarn init 此命令会引导您创建一个新的package.json文件,用于记录项目的元信息和依赖。 添加依赖&…...
如何在Bash中连接字符串变量
问题: 在 PHP 中,字符串按如下方式连接在一起: $foo "Hello"; $foo . " World";在这里,$foo 变成了 "Hello World"。 在 Bash 中如何实现这一点? 回答1: foo"Hello" fo…...
doesn‘t contain a valid partition table
查看硬盘空间 $ fdisk -l Disk /dev/mmcblk0: 29 GB, 31037849600 bytes, 60620800 sectors 947200 cylinders, 4 heads, 16 sectors/track Units: sectors of 1 * 512 512 bytesDisk /dev/mmcblk0 doesnt contain a valid partition table Disk /dev/mmcblk0p1: 1 MB, 10485…...
modprobe加载驱动模块时报错:modprobe: module xxx.ko not found in modules.dep
问题 使用modprobe时,报错modprobe: module xxx.ko not found in modules.dep: 原因 加载模块时,依赖没法正确添加 解决 在使用modprobe前,调用一下depmod指令,之后再用modprobe加载驱动模块 depmod modprobe interr…...
游戏引擎中的粒子系统
一、粒子基础 粒子系统里有各种发射器(emitter),发射器发射粒子(particle)。 粒子是拥有位置、速度、大小尺寸、颜色和生命周期的3D模型。 粒子的生命周期中,包含产生(Spawn)、与环…...
哈佛大学商业评论 -- 第二篇:增强现实是如何工作的?
AR将全面融入公司发展战略! AR将成为人类和机器之间的新接口! AR将成为人类的关键技术之一! 请将此文转发给您的老板! --- 本文作者:Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的,但大…...
『python爬虫』巨量http代理使用 每天白嫖1000ip(保姆级图文)
目录 注册 实名得到API链接和账密 Python3requests调用Scpay总结 欢迎关注 『python爬虫』 专栏,持续更新中 欢迎关注 『python爬虫』 专栏,持续更新中 注册 实名 注册巨量http 用户概览中领取1000ip,在动态代理中使用.用来测试一下还是不错的 得到AP…...
6-95 希尔排序(Java语言描述)
编程实现希尔排序函数。public static void shellSort(int arr[])。其中arr存放待排序的数据,数组长度不大于1000。 函数接口定义: /* 对长度为n的数组arr执行希尔排序 */ public static void shellSort(int arr[]); 请实现 shellSort函数,使排序后的数据从小到大排列。…...
JAVA面试大全之分布式篇
目录 1、一致性算法 1.1、什么是分布式系统的副本一致性?有哪些? 1.2、在分布式系统中有哪些常见的一致性算法?...
qt各种锁使用讲解
在Qt中,主要有以下几种锁的类型: 1. QMutex(互斥锁): 是最常见的锁类型,用于实现简单的互斥访问。可以通过lock()和unlock()手动控制锁的加锁和解锁。 QMutexLocker:是一个RAII类,…...
5.111 BCC工具之ext4dist.py解读
一,工具简介 ext4dist跟踪ext4的读取、写入、打开和fsync操作,并将其延迟总结为2的幂次方直方图。 二,代码示例 #!/usr/bin/env pythonfrom __future__ import print_function from bcc import BPF from time import sleep, strftime import argparse# symbols kallsyms …...
Rust 的 termion 库控制终端光标的位置
在控制台应用程序中,固定打印在屏幕的第一行通常涉及到控制终端光标的位置。Rust 标准库本身并不提供直接控制终端光标位置的功能,但你可以使用第三方库如 termion 来实现这个需求。 termion 是一个用于处理终端的 Rust 库,它提供了很多有用…...
ADB(Android Debug Bridge)操作命令详解及示例
ADB(Android Debug Bridge)是一个强大的命令行工具,它是Android SDK的一部分,主要用于Android设备(包括真实手机和平板电脑以及模拟器)的调试、系统控制和应用程序部署。 下面是一些ADB的常用命令ÿ…...
书生浦语训练营2期-第二节课笔记作业
目录 一、前置准备 1.1 电脑操作系统:windows 11 1.2 前置服务安装(避免访问127.0.0.1被拒绝) 1.2.1 iis安装并重启 1.2.2 openssh安装 1.2.3 openssh服务更改为自动模式 1.2.4 书生浦语平台 ssh配置 1.3 补充(前置服务ok…...
【日常积累】指定ruby版本环境安装
背景说明 在redis的5.0版本之前,使用redis提供的redis-trib创建redis集群时还需要依赖ruby环境。当然有时候我们自已也需要安装指定ruby版本环境。下面是安装时的大致过程,以及过程中遇到的问题解决。我使用的环境是centos7,小版本差别应该不…...
SOC内部集成网络MAC外设+ PHY网络芯片方案:MII/RMII 接口与 MDIO 接口
一. 简介 本文来了解一下常用的一种网络硬件方案:SOC内部集成网络MAC外设 PHY网络芯片方案。 其中涉及的 MII接口,RMII接口(MII接口与RMII接口二选一),MDIO接口,RJ45。 二. MII/RMII 接口,M…...
简单了解HTTP和HTTPS
HTTP的安全问题? 我们都知道HTTP是不安全的,而HTTPS是安全的,那HTTP有哪些安全问题呢?(考虑传输过程以及响应方) 明文传输,有窃听风险:HTTP协议无法加密数据,所有通信数…...
系列学习前端之第 9 章:一文搞懂 Node.js 和 nvm,掌握 npm
1、说说 Node.js Node.js 本质上是一款应用软件(本质上与QQ、微信一样),它可以运行 JavaScript 代码,这样就使得 JavaScript 能够脱离浏览器运行。Node.js 是基于 Google 的 V8 引擎,V8引擎执行 Javascript 的速度非常…...
超强命令行解析工具Apache Commons CLI
概述 为什么要写这篇文章呢?因为在读flink cdc3.0源码的时候发现了这个工具包,感觉很牛,之前写过shell命令,shell是用getopts来处理命令行参数的,但是其实写起来很麻烦,长时间不写已经完全忘记了,现在才发现原来java也有这种工具类,所以先学习一下这个的使用,也许之后自己在写…...
JAVAEE——多线程进阶,锁策略
文章目录 锁策略乐观锁和悲观锁乐观锁悲观锁两者的比较 读写锁重量级锁和轻量级锁重量级锁轻量级锁 自旋锁公平锁和非公平锁公平锁非公平锁 可重入锁和不可重入锁可重入锁不可重入锁 锁策略 乐观锁和悲观锁 乐观锁 什么是乐观锁呢?我们可以认为乐观锁比较自信&am…...
富文本编辑器Quill全套教程
Quill简介 Quill是一款现代的富文本编辑器,它以其API驱动的设计和对文本格式的深度理解而著称。与传统的富文本编辑器不同,Quill专注于以字符为中心,构建了一个直观且易于使用的API,使得开发者能够轻松地对文本进行格式化和编辑。…...
Swift 代码注释的使用
Swift代码注释的使用 在 iOS 开发中,代码注释是一种很好的实践,可以帮助他人更容易理解你的代码。通常可以在代码中使用注释来解释代码的功能、目的、实现细节等。下面是一些常见的 iOS 代码注释示例: 1. 单行注释: // 这是一个…...
蓝桥杯—DS1302
目录 1.管脚 2.时序&官方提供的读写函数 3.如何使用读写函数 4.如何在数码管中显示在DS1302中读取出的数据? 1.管脚 2.时序&官方提供的读写函数 /* # DS1302代码片段说明1. 本文件夹中提供的驱动代码供参赛选手完成程序设计参考。2. 参赛选手可以自行…...
nginx: 集群环境配置搭建
nginx 集群环境搭建 1 ) 概述 nginx 本身就应该选择性能强劲的机器同时为了满足更多流量的需求, 多台nginx 机器做集群来满足强大的需求故而,我们需要一个负载均衡器,以及多台nginx的机器 这里负载均衡器应该有主从和热备,目前先使用一台来描…...
Linux:进程终止和等待
一、进程终止 main函数的返回值也叫做进程的退出码,一般0表示成功,非零表示失败。我们也可以用不同的数字来表示不同失败的原因。 echo $?//打印最近一次进程执行的退出码 而作为程序猿,我们更需要知道的是错误码所代表的错误信息&#x…...
一、next-auth 身份验证凭据-使用电子邮件和密码注册登录
一、next-auth 身份验证凭据-使用电子邮件和密码注册登录 文章目录 一、next-auth 身份验证凭据-使用电子邮件和密码注册登录一、前言二、前置准备1、环境配置2、相关库安装(1)vercel 配置(2)Yarn 包管理配置 3、next项目初始化与…...
2.SpringBoot利用Thymeleaf实现页面的展示
什么是Thymeleaf? Thymeleaf是一个现代服务器端Java模板引擎,适用于Web和独立环境,能够处理HTML,XML,JavaScript,CSS甚至纯文本。 Thymeleaf的主要目标是提供一种优雅且高度可维护的模板创建方式。为实现这…...
国外网站网页设计/网络推广竞价外包
UPS不间断电源的通信接口越来越多,而且因为 UPS非常易于扩展的特性,使用通信口的智能设备越来越多,成为一种潮流和趋势。UPS电源是机房设备中是非常重要的一个成员,其因它的电路简单,可靠性以及效率高,过载…...
网页制作实践 做网站/互联网营销师培训内容
借鉴php安装错误 2013-01-04 19:16:49分类:系统运维环境:centos X64 最小化安装php版本:php-5.4.3安装前.先安装些软件和库文件yum install -y gcc gcc-c make zlib zlib-devel pcre pcre-devel libjpeg libjpeg-devel libpng libpng-devel…...
棠下手机网站建设报价/网络公司seo推广
准备工作 软件下载地址 VMware 14_32/64位破解版 断网系统支持win7/8/10 安装步骤 1.先使用“百度网盘客户端”下载VMware14软件安装包到电脑磁盘里,并解压缩,安装前先断开电脑网络,然后找到VMware-workstation-full-14.0.exe,…...
wordpress在哪修改代码/线上引流线下推广方案
查mysql bin-logbinlog基本定义:二进制日志,也成为二进制日志,记录对数据发生或潜在发生更改的SQL语句,并以二进制的形式保存在磁盘中; 作用:MySQL的作用类似于Oracle的归档日志,可以用来查看数…...
济南网站建设用途/重庆百度快速优化
OperaMasks-UI是一款基于jQuery并提供丰富组件的前端UI库,拥有丰富的业务组件、强大的扩展能力、高度的可靠性,满足大部分业务场景需求,带给你便捷的前端开发新体验。 官网地址: http://ui.operamasks.org/在线演示: h…...
网站建设一般多少钱新闻/百度关键词快速排名方法
1.IN 操作符 在业务密集的SQL当中尽量不采用IN操作符而使用EXISTS 2.NOT IN 操作符 强列推荐不使用3. <> 操作符 强列推荐不使用 用其它相同功能的操作运算代替, 如 a<>0 改为 a>0 or a<0 ;a<>’’ 改为 a>’’ 4. > < 操作符 推荐 5. LIKE 操…...