DP算法:动态规划算法
步骤
(1)确定初始状态
(2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来
(3)确定边界条件。
例题
蓝桥杯——印章(python实现)

使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率
i表示买的印章数,j表示凑齐的印章种数
情况一:如果i<j,不可能凑齐印章,概率为0
情况二:如果j=1,dp[i][1] = n*((1/n)**i),凑齐一种印章,所有i个印章为一个种类,这一个种类有n种情况可选
情况三:凑齐j种印章。前面买了i-1个印章。可能前面i-1步凑够了j种印章,那么只用从j种里随意选出来一个dp[i-1][j]*j*p;可能前面i-1步凑够了j-1种印章,那么从剩下的n-j+1种里选出来一个dp[i-1][j-1]*(n-j+1)*p,因此为dp[i][j] = dp[i-1][j]*j*p+dp[i-1][j-1]*(n-j+1)*p
strs = input().strip().split()
n = int(strs[0])
m = int(strs[1])# 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率
dp = [[0]*(n+1) for _ in range(m+1)]p = 1.0/nfor i in range(1,m+1):for j in range(1,n+1):# 如果i<j,不可能凑齐印章if i<j:dp[i][j] = 0# 如果凑齐一种印章elif j==1:dp[i][1] = n*(p**i)# 凑齐j种印章:可能前面i-1步凑够了j种印章,那么只用从j种里随意选出来一个;# 可能前面i-1步凑够了j-1种印章,那么从剩下的n-j+1种里选出来一个else:dp[i][j] = dp[i-1][j]*j*p+dp[i-1][j-1]*(n-j+1)*p
print('%.4f'%(dp[m][n]))
相关文章:
DP算法:动态规划算法
步骤(1)确定初始状态(2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来(3)确定边界条件。例题蓝桥杯——印章(python实现)使用dp记录状态,d…...
一三四——一六七
一三四、JavaScript——_DOM简介 MDNq前端参考文档:DOM 概述 - Web API 接口参考 | MDN (mozilla.org) 一三五、JavaScript——HelloWorld <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta h…...
day29_JS
今日内容 上课同步视频:CuteN饕餮的个人空间_哔哩哔哩_bilibili 同步笔记沐沐霸的博客_CSDN博客-Java2301 零、 复习昨日 一、事件 二、DOM操作 三、案例 零、 复习昨日 js 脚本语言,弱类型 引入方案: 3种 js的内容: 语法dombom 语法 变量 var 数据类型 引用类型 - 对象,J…...
【HTTP协议与Web服务器】
HTTP协议与Web服务器浏览器与服务器通信过程HTTP的请求报头HTTP请求报头结构HTTP的请求方法HTTP应答报头HTTP应答报头结构应答状态web服务器的c语言实现浏览器与服务器通信过程 浏览器与Web服务器再应用层通信使用的是HTTP协议,而HTTP协议在传输层使用的是TCP协议。…...
Idea+maven+spring-cloud项目搭建系列--12 整合grpc
前言: grpc 是geogle 开源的rpc 通信框架,通过定义proto生成通信存根,像本地调用服务一样,进行远程服务的调用; 1 消费端服务提供: 1.1 引入grpc 和 protobuf <!-- RPC --> <!-- RPC 服务调用 …...
Revit开洞问题:结构专业开洞口剖面显示及一键开洞
一、Revit中关于结构专业开洞口剖面显示问题 Revit作业的时候,我们不仅只为了一个最后的三维立体模型,我们需要的是一个符合国家以及本院制图标准的一个出图样式,这时候就会出现各种各样的显示问题,本期就一个结构专业开洞显示问题,跟大家一起…...
0107连通分量-无向图-数据结构和算法(Java)
文章目录1 API2 代码实现和分析测试后记1 API 深度优先搜索下一个直接应用就是找出一幅图中的连通分量,定义如下API。 public class CCCC(Graph g)预处理构造函数booleanconnected(int v, int w)v和w连通吗intcount()连通分量数intid(int v)v所在的连通分量标识符(0~count()-…...
[学习笔记]黑马程序员python教程
文章目录思维导图Python基础知识图谱面向对象SQL入门和实战Python高阶技巧第一阶段第九章:Python异常、模块与包1.9.1异常的捕获1.9.1.1 为什么要捕获异常1.9.1.2 捕获常规的异常1.9.1.3 捕获指定的异常1.9.1.4 捕获多个异常1.9.1.5 捕获全部异常1.9.1.6 异常的else…...
如何配置用于构建 FastReport Online Designer 的 API ?
FastReport Online Designer 是一个跨平台的报表设计器,允许通过任何平台的移动设备创建和编辑报表。今天我们就一起来看看在2023版中新增和改进的功能有哪些,点击下方可以获取最新版免费试用哦! FastReport Onlin Designe最新版试用https:/…...
【嵌入式Linux内核驱动】02_字符设备驱动
字符设备驱动 〇、基本知识 设备驱动分类 (按共性分类方便管理) 1.字符设备驱动 字符设备指那些必须按字节流传输,以串行顺序依次进行访问的设备。它们是我们日常最常见的驱动了,像鼠标、键盘、打印机、触摸屏,还有…...
【零散整理】
1-1 git查看代码的项目总行数 git log --prettytformat: --numstat | awk ‘{ add $1; subs $2; loc $1 - $2 } END { printf “added lines: %s, removed lines: %s, total lines: %s\n”, add, subs, loc }’ - 1-2 cookie const cookies document.cookie.split(; )for…...
RocketMQ重复消费的症状以及解决方案
RocketMQ重复消费的症状以及解决方案 生产消息时重复 症状 当一条消息已被成功发送到 消费者 并完成持久化,此时出现了网络闪断或者客户端宕机,导致服务端对客户端应答失败。 如果此时 生产者 意识到消息发送失败并尝试再次发送消息,消费者…...
数字化时代,企业的商业模式建设
随着新一代信息化、数字化技术的应用,众多领域通过科技革命和产业革命实现了深度化的数字改造,进入到以数据为核心驱动力的,全新的数据处理时代,并通过业务系统、商业智能BI等数字化技术和应用实现了数据价值,从数字经…...
项目实战典型案例23——-注册上nacos上的部分服务总是出现频繁掉线的情况
注册上nacos上的部分服务总是出现频繁掉线的情况一:背景介绍二:思路&方案解决问题过程涉及到的知识nacos服务注册和服务发现一:背景介绍 spring cloud项目通过nacos作为服务中心和配置中心,出现的问题是其中几个服务总是出现…...
玩转金山文档 3分钟让你的文档智能化
在上个月底,我们给大家推荐了金山轻维表的几个使用场景,社群中不少用户反响很好,对其中一些场景的解决方案十分感兴趣。但也有一些人表示,有些场景不知道如何实现,希望我们能提供模版/教程。这次我们将做一期热门模板盘…...
安装了nodejs怎么安装nvm
第一步,从控制面板卸载已经安装的node 第二步,删除C盘program开头文件夹下的node文件 第三步,去C/user/用户名 文件夹下,删除.npmrc文件 第四步,打开隐藏文件,第三步文件夹下有一个Appdata文件ÿ…...
java安全编码规范考试
java安全编码规范考试 整理不易,收点币!! 安全编码规范考试.md 下面对zip文件的安全解压缩描述,错误的是 A.zip文件解压时,可以使用entry.getSize()对解压缩文件进行文件大小判断 B.zip文件解压时&…...
表格检测识别技术的发展历程
近年来,随着计算机技术的飞速发展,越来越多的研究者开始关注表格检测识别技术。表格检测识别技术是一种利用计算机自动处理表格的技术,它可以实现从文本中检测出表格,并进行识别和提取。这种技术有助于提高文本处理的效率…...
设计UI - Adobe xd对象介绍
矩形工具 新建矩形 操作步骤:选择矩形工具,快捷键R,鼠标在画板上拖出矩形即可。 拖动定界框周围圆形手柄,可快速调整矩形大小,也可以输入宽和高的参数对矩形大小进行改变。 移动矩形 操作步骤:选择选择工具…...
优思学院|精益生产中的“单件流”真的能够做到吗?
精益生产中提到的“一个流”(One Piece Flow)是一种生产方式,它的核心理念是通过合理配置作业场地、人员和设备,使产品从投入到成品产出的整个制造加工过程中始终处于不停滞、不堆积、不超越,按节拍一个一个地流动。 …...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
