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)是一种生产方式,它的核心理念是通过合理配置作业场地、人员和设备,使产品从投入到成品产出的整个制造加工过程中始终处于不停滞、不堆积、不超越,按节拍一个一个地流动。 …...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
