【dp动态规划】印章

这篇具有很好参考价值的文章主要介绍了【dp动态规划】印章。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。

输入格式

一行两个正整数n和m

输出格式

一个实数P表示答案,保留4位小数。

样例输入

2 3

样例输出

0.7500

思路

创建m+1行 n+1列的二维数组
若从键盘输入4 3
dp = [
        [0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0]
    ]

python代码文章来源地址https://www.toymoban.com/news/detail-431393.html

#创建二位数组
n,m = map(int,input().split())
#将数组初始化为0
dp = [[0 for i in range(n + 1)] for j in range(m + 1)]

for i in range(1 , m + 1):
    for j in range(1 , n + 1):
        if i < j :
            dp[i][j] = 0
        elif j == 1:
            dp[i][j] = pow(1 / n ,i - 1)
        else:
            dp[i][j] = dp[i-1][j] * (1/n) * j + dp[i-1][j-1] * (1/n)*(n-(j-1))

print("{:.4f}".format(dp[m][n]))

到了这里,关于【dp动态规划】印章的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】简单多状态dp问题(2)买卖股票问题

    买卖股票问题 传送门:力扣309. 最佳买卖股票时机含冷冻期 题目: 1.1 题目解析 越难的dp问题,看示例只能起到了解题目的效果,一般推不出啥普遍的规律,所以接下来就是我们的算法原理,通过动归的思想去理解,才会豁然开朗! 1.2 算法原理 1.2.1 状态表示 我们需要通过经

    2024年02月12日
    浏览(56)
  • 动态规划:两个数组的dp问题(C++)

    动态规划往期文章: 动态规划入门:斐波那契数列模型以及多状态 动态规划:路径和子数组问题 动态规划:子序列问题 动态规划:回文串问题 1.最长公共子序列(中等) 链接 :最长公共子序列 题目描述 做题步骤 状态表示 对于两个数组的dp,采用一维dp是没有办法清晰的表

    2024年02月08日
    浏览(51)
  • C++ 动态规划 数位统计DP 计数问题

    给定两个整数 a 和 b ,求 a 和 b 之间的所有数字中 0∼9 的出现次数。 例如,a=1024,b=1032 ,则 a 和 b 之间共有 9 个数如下: 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 10 次,1 出现 10 次,2 出现 7 次,3 出现 3 次等等… 输入格式 输入包含多组测试数据。 每组测试数据占一

    2024年02月20日
    浏览(42)
  • C++--动态规划两个数组的dp问题

    1.最长公共子序列  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给定两个字符串  text1 和  text2 ,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的

    2024年02月10日
    浏览(41)
  • 【动态规划】LeetCode 312. 戳气球 --区间DP问题

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月16日
    浏览(39)
  • 【动态规划】简单多状态dp问题(1)打家劫舍问题

    打家劫舍问题 传送门:面试题 17.16. 按摩师 题目: 1.1 题目解析 越难的dp问题,看示例只能起到了解题目的效果,一般推不出啥普遍的规律,所以接下来就是我们的算法原理,通过动归的思想去理解,才会豁然开朗! 1.2 算法原理 1.2.1 状态表示 我们需要通过经验 + 题目要求去

    2024年02月12日
    浏览(43)
  • 动态规划课堂7-----两个数组的dp问题(等价代换)

    目录 引言: 例题1:最长公共子序列 例题2:不同的子序列 例题3:通配符匹配 例题4:正则表达式 结语: 本节我们就要进入 两个数组的dp问题 的学习,通过前面几个章节的学习,相信友友们对动态规划的解题步骤和代码编写步骤已经有了一定的了解(*/ω\*),接下来我会通过

    2024年03月22日
    浏览(39)
  • 算法沉淀 —— 动态规划篇(简单多状态dp问题上)

    几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此 1.、状态表示:通常状态表示分为以下两种,其中更是第一种为主。 以i为结尾 ,dp[i] 表示什么,通常为代求问题(具体依题目而定) 以i为开始 ,dp[i]表示什么,通常为代求问题(具体依题目而

    2024年04月11日
    浏览(44)
  • C++ DP算法,动态规划——背包问题(背包九讲)

    有N件物品和一个容量为 V V V 的背包。放入第i件物品耗费的空间是 C i C_i C i ​ ,得到的价值是 W i W_i W i ​ 。 求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即 F [ i , v ] F[i, v] F

    2024年02月16日
    浏览(51)
  • 算法沉淀 —— 动态规划篇(简单多状态dp问题下)

    几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此 1.、状态表示:通常状态表示分为基本分为以下两种,其中更是以第一种为甚。 以i为结尾 ,dp[i] 表示什么,通常为代求问题(具体依题目而定) 以i为开始 ,dp[i]表示什么,通常为代求问题(具

    2024年04月16日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包