DP算法:动态规划算法

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

步骤

(1)确定初始状态

(2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来

(3)确定边界条件。

例题

  1. 蓝桥杯——印章(python实现)

DP算法:动态规划算法

使用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/n

for 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]))
  1. 蓝桥杯——算法训练 拿金币

DP算法:动态规划算法

使用dp记录状态,dp[i][j]表示在arr[i][j]可以拿到的最多金币数。

情况一:如果i=j=0,那么此位置最多拿到金币数dp[0][0]=arr[0][0]

情况二:如果i=0,那么无法从上方转移,只能从左边转移到arr[0][j]。dp[0][j] = dp[0][j - 1] + arr[0][j]左边位置的最大金币数加上当前位置arr[0][j]的金币数

情况三:如果j=0,那么无法从左方转移,只能从上边转移到arr[i][0]。dp[i][0] = dp[i - 1][0] + arr[i][0]上边位置的最大金币数加上当前位置arr[i][0]的金币数

情况四:如果i,j != 0,dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j],当前位置金币数arr[i][j]加上左边和上边dp中最大的一个 max(dp[i - 1][j], dp[i][j - 1]) 文章来源地址https://www.toymoban.com/news/detail-468892.html

n = int(input())
strs = [(input()).strip().split() for _ in range(n)]
arr = []
for i in range(n):
    temp = []
    j = 0
    while j < len(strs[i]):
        temp.append(int(strs[i][j]))
        j += 1
    arr.append(temp)

dp = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == 0 and j == 0:
            dp[0][0] = arr[0][0]
        if i == 0:
            dp[0][j] = dp[0][j - 1] + arr[0][j]
        if j == 0:
            dp[i][0] = dp[i - 1][0] + arr[i][0]
        if i != 0 and j != 0:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j]

print(max(max(dp)))

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

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

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

相关文章

  • 动态规划——状态转移方程

    DP问题的核心即确定动态转移方程。 (1)寻找变量,确定子问题。DP表一般为二维,故需要两个变量。 (2)寻找总问题与子问题迭代关系,确定中间值、迭代值 例1: 有5个物品,其重量分别是{2, 2, 6, 5, 4},价值分别为{6, 3, 5, 4, 6},背包的容量为10,计算背包所能装入物品的

    2023年04月08日
    浏览(35)
  • 10 | 动态规划(下):如何求得状态转移方程并进行编程实现?

    上一节,从查询推荐的业务需求出发,介绍了编辑距离的概念,今天我们要基于此,来获得状态转移方程,然后才能进行实际的编码实现。 状态转移方程和编程实现 上一节讲到了使用状态转移表来展示各个子串之间的关系,以及编辑距离的推导。不过,没有完成那张表格。

    2024年04月27日
    浏览(35)
  • 动态规划——用带权的有向图描述状态的转移

    此文章的作用:教会读者用 简单、快速、稳定 的方法推出 线性 DP的转移方程。 笔者希望通过一些题教会读者做所有线性DP的方法,而不是只教会读者这些题的解法。 我们发现:店铺越多,可以偷的店铺就越多,能得到的现金就越多。 举例:如果只有一家店铺,你就只能偷

    2024年04月17日
    浏览(34)
  • 「动态规划」简单多状态dp问题

    以经典问题“打家劫舍”来解释简单多状态dp问题和解决方法 题目链接:打家劫舍I 这种问题就是在某一个位置有多个状态可以选择,选择 不同的状态 会影响 最终结果 在这道题中就是小偷在每一个房屋,可以选择偷或不偷,每一次选择都会影响最终偷窃金额 状态表示 因为

    2024年03月15日
    浏览(56)
  • 【动态规划】简单多状态dp问题(2)买卖股票问题

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

    2024年02月12日
    浏览(56)
  • C++ 动态规划 状态压缩DP 最短Hamilton路径

    给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数 n 。 接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[

    2024年02月19日
    浏览(40)
  • 【动态规划】简单多状态dp问题(1)打家劫舍问题

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

    2024年02月12日
    浏览(42)
  • 【动态规划专栏】专题三:简单多状态dp--------3.删除并获得点数

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年03月22日
    浏览(43)
  • 【状态机dp 动态规划】100290. 使矩阵满足条件的最少操作次数

    动态规划汇总 状态机dp 给你一个大小为 m x n 的二维矩形 grid 。每次 操作 中,你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后,你需要确保每个格子 grid[i][j] 的值满足: 如果下面相邻格子存在的话,它们的值相等,也就是 grid[i][j] == grid[i + 1][j](如果存在)

    2024年04月24日
    浏览(35)
  • 【动态规划 状态机dp 性能优化】3098. 求出所有子序列的能量和

    动态规划 状态机dp 性能优化 给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。 一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。 请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。 由于答案可能会很大,将答案对 109 + 7 取余 后返回。 示

    2024年04月27日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包