【入门dp】力扣鸡蛋掉落问题和转账问题的关系初探

这篇具有很好参考价值的文章主要介绍了【入门dp】力扣鸡蛋掉落问题和转账问题的关系初探。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

我昨晚偶然编出了一道水题,名为转账问题:已知银行卡里有不超过n元,你想把卡里所有钱提到某信支付,但你无法看到卡里的钱,你只能执行若干次转账i元的操作,每次看到转账成功与失败的提示。问至少需要操作多少次。ni是自然数。形式化描述:你的策略y是一段代码,初始输入为n,代码对于实际的i = 1~n元各有一个需要的猜测次数x[i],则y = max(x[i] for i in range(1, n + 1)),所求为min(y for y in y_set)

本文CSDN:https://blog.csdn.net/hans774882968/article/details/131749241

本文juejin:https://juejin.cn/post/7255967761805197349

本文52pojie:https://www.52pojie.cn/thread-1809085-1-1.html

作者:hans774882968以及hans774882968以及hans774882968

思路

尝试转i元,1 <= i <= n。如果成功,则知道卡里不超过n - i元;如果失败,则知道卡里不超过i - 1元。因此定义dp[i]为已知银行卡里有不超过i元时的最少操作次数。边界条件:dp[0~2] = 0~2。状态转移方程:dp[i] = min(max(dp[i - j], dp[j - 1]) + 1) for j in range(1, i + 1)

接下来考虑优化这个dp转移。有一个很明显的单调性:v1 < v2dp[v1] <= dp[v2]i - j单减,j - 1单增,因此取i - j == j - 1j即为最优点。

  • i为奇数,则dp下标取到(i - 1) // 2
  • i为偶数,则dp下标取到(i - 1) // 2 + 1

取到下标可统一为i // 2。因此转移方程可以简化为:dp[i] = dp[i // 2] + 1。对于n,答案居然就是n二进制数位的个数!

于是有推论:最优策略为:总是尝试转i - i // 2 = (i + 1) // 2元。

与力扣鸡蛋掉落问题的关系

鸡蛋掉落问题传送门

经群友提醒,这个问题从状态转移方程的角度来看,和鸡蛋掉落问题的k = +∞的情况类似。两个问题从题面来看不像,但它们有一个相同点:1次操作无论获得什么反馈,都能缩小问题规模。因此我们写了下面的代码,验证k = n, n+1, n+2的情况下所得的dp数组不仅相等,还等于转账问题的dp数组。文章来源地址https://www.toymoban.com/news/detail-597649.html

代码

import numpy as np


def main():
    N = 2001

    dp1 = [[0] * N for _ in range(N + 2)]

    def egg_drop(k, n):
        for j in range(1, n + 1):
            dp1[1][j] = j
        for i in range(2, k + 1):
            best = 1
            for j in range(1, n + 1):
                while best <= j and dp1[i][j - best] > dp1[i - 1][best - 1]:
                    best += 1
                dp1[i][j] = 1 + min(dp1[i][j - best + 1], dp1[i - 1][best - 1])

    dp2 = np.array([0] * N)

    def bin_count(n):
        for i in range(1, n + 1):
            dp2[i] = dp2[i // 2] + 1

    dp3 = np.array([N] * N)

    def n2_dp(n):
        dp3[0] = 0
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                dp3[i] = min(dp3[i], max(dp3[i - j], dp3[j - 1]) + 1)

    egg_drop(N + 1, N - 1)
    bin_count(N - 1)
    n2_dp(N - 1)
    ans1 = np.array([dp1[i][i] for i in range(N)])
    ans2 = np.array([dp1[i + 1][i] for i in range(N)])
    ans3 = np.array([dp1[i + 2][i] for i in range(N)])
    assert (ans1 == dp2).all() and (ans2 == dp2).all() and (ans3 == dp2).all() and (dp2 == dp3).all()
    print('dp2 ', dp2[:101])
    print('dp3 ', dp3[:101])
    print('ans3', ans3[:101])


if __name__ == '__main__':
    main()

到了这里,关于【入门dp】力扣鸡蛋掉落问题和转账问题的关系初探的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • dp算法 力扣174地下城游戏

    在学习编程时,算法是一道硬菜,而dp作为算法的一份子,它的地位在编程界举足轻重。 174. 地下城游戏 - 力扣(LeetCode) 本文是Java代码哦~ 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上

    2024年02月16日
    浏览(43)
  • dp算法 力扣152乘积最大子数组

    本文是Java代码!! 152. 乘积最大子数组 - 力扣(LeetCode) 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 示例 1: 输入

    2024年02月13日
    浏览(42)
  • 「数位dp」统计整数数目(力扣第2719题)

    本题为1月16日力扣每日一题 题目来源:力扣第2719题 题目tag: 数位dp 动态规划 给你两个数字字符串num1和num2,以及两个整数max_sum和min_sum。如果一个整数x满足以下条件,我们称它是一个好整数: (num1 leq x leq num2) (min_sum leq digit_sum(x) leq max_sum) 请你返回好整数的数目。答案

    2024年01月16日
    浏览(40)
  • 力扣hot100 杨辉三角 递归 DP

    Problem: 118. 杨辉三角 👨‍🏫 参考地址 时间复杂度: 添加时间复杂度, 示例: O ( n ) O(n) O ( n ) 空间复杂度: 添加空间复杂度, 示例: O ( n ) O(n) O ( n )

    2024年01月17日
    浏览(39)
  • dp算法 力扣309最佳买卖股票时机含冷冻期

    给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 注意:你不能同时参与多笔交

    2024年02月14日
    浏览(41)
  • 力扣hot100 打家劫舍 DP 滚动数组

    Problem: 198. 打家劫舍 👨‍🏫 参考地址 时间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( 1 ) O(1) O ( 1 )

    2024年01月19日
    浏览(42)
  • 力扣hot100 最长递增子序列 线性DP 贪心 二分

    Problem: 300. 最长递增子序列 时间复杂度: O ( n 2 ) O(n^2) O ( n 2 ) 空间复杂度: O ( n ) O(n) O ( n ) 👨‍🏫 参考题解 时间复杂度: O ( n log ⁡ n ) O(nlog{n}) O ( n lo g n ) 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月20日
    浏览(41)
  • 动态规划(一):从递归转变为dp ——力扣 983 最低票价

    (1)动态规划表就是装递归返回值的容器 (2)动态转移方程等价于递归中的尝试策略 (3)递归中各 if 判断条件就是尝试策略的分类,对应了动态转移方程 (4)想象一个二叉树,递归(记忆化)是从顶到底,顶可分出多种情况,而到底就是结束,不会再有分类,因此是从

    2024年04月10日
    浏览(33)
  • 【力扣周赛】第 113 场双周赛(贪心&异或性质&换根DP)

    https://leetcode.cn/contest/biweekly-contest-113/ https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/ 提示: 1 = nums.length = 100 1 = nums[i] = 100 nums 中的整数互不相同。 因为数据范围很小,所以可以从小到大枚举可能的答案。 https://leetcode.cn/problems/minimum-array-length-after-pair-removals/ 提示: 1

    2024年02月07日
    浏览(34)
  • Android UI设计中px、pt、ppi、dpi、dp、sp之间的关系

    做了几个移动端的项目之后,深感UI设计移动端尺寸换算的必要性,在此做个总结。 先介绍下各自的定义: px: pixel,像素,电子屏幕上组成一幅图画或照片的最基本单元 pt: point,点,印刷行业常用单位,等于1/72英寸 ppi: pixel per inch,每英寸像素数,该值越高,则屏幕越细腻

    2024年02月07日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包