动态规划的万能公式(三类题型)

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

做你想做的,错的算我的

这里是Want595,欢迎光临我的世界 ~ 

目录

前言 

一、斐波那契式

通项公式:f(n)=f(n-1)+f(n-2) 

举例说明

爬楼梯 

骨牌铺方格 

一只小蜜蜂

二、背包问题

通项公式:f(i,j)=max(f(i-1,j),f(i-1(或i),j-w(i))+v(i)) 

举例说明 

0-1背包问题 

完全背包问题 

矿工问题

三、最长递增子列

通项公式:f(i,j)=max(f(i),f(j)+1)

举例说明 

最长递增子序列

最少拦截系统 

文章目录


前言 

本文主要介绍如何用Python解决动态规划的问题,在动态规划问题中,最主要的是找到问题的dp,即找到状态转移函数,当你找到了该问题的状态转移函数,你就成功了一半,下面我将介绍三类最主要的题型,对于这三类题型,分别有着不同的解题公式。

一、斐波那契式

这一类题型基本都有一定的规律,一般思维是从最后往前推,找出状态转移函数。 

通项公式:f(n)=f(n-1)+f(n-2) 

def f(n):
    if n<?:       #首先需要单独考虑几个特别的值
        return
    ……
    if n==t:
        return
    a,b=?,?     
    for i in range(t,n):
        sums=a+b  #该句其实就是动态规划(根据具体情况而改变),表示当前的方法数实际上是前面两个方法数之和
        a=b
        b=sums
    return sums

举例说明

爬楼梯 

【问题描述】

假设小明住在二楼,每次回家都需要经过一个有n层台阶的楼梯。

小明每次可以选择一步走一级台阶或者一步走两级台阶。

请计算一下小明从楼下到家一共有多少种走法?

【输入形式】

整数n,表示一共有几层台阶

【输出形式】

一行,表示一共有多少种走法

【样例输入】

10

【样例输出】

89

def Climb(n):     #定义的爬楼梯函数
    if n<1:       #判断是否合法,台阶不合法,返回0
        return 0 
    if n==1:      #当只有一层台阶时,一种走法
        return 1
    if n==2:      #当有两层台阶时,两种走法
        return 2
    a,b=1,2       #当台阶数大于3时,我们发现走法数呈斐波那契排列
    sums=0        #即每一层台阶的走法数等于前两层台阶走法数的和
    for i in range(2,n):     #这是为什么呢,因为我们知道,每次只能走1步或者2步
        sums=a+b      #倒推一下,我们如何能到达第n级台阶呢,有两种方法
        a=b           #一种是在第9层台阶再走1步,另一种是在第8层台阶再走2步
        b=sums        #而到达第9层也是两种方法,在第7层走两步或在第8层走一步
    return sums      #同理所以我们只需要n层前两层走的步数和即可
n=int(input())        #而前两层又等于前前两层……,是个斐波那契数列
print(Climb(n))

骨牌铺方格 

【问题描述】

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:

【输入形式】

输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

【输出形式】

对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。

【样例输入】

1

3

2文章来源地址https://www.toymoban.com/news/detail-443520.html

【样例输出】

1

3

2

while(1):
    def get(n):
        if n<1:
            return 0
        if n==1:
            return 1
        if n==2:
            return 2
        a,b=1,2
        for i in range(2,n):
            sums=a+b
            a=b
            b=sums
        return sums
    n=int(input())
    print(get(n))

一只小蜜蜂

【问题描述】

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 其中,蜂房的结构如下所示。

动态规划的万能公式(三类题型)

【输入形式】

输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0<a<b<50)。

【输出形式】

对于每个测试实例,请输出蜜蜂从蜂房a爬到蜂房b的可能路线数,每个实例的输出占一行。

【样例输入】

2

1 2

3 6

【样例输出】

1

3

def methods(a,b):
    t=b-a
    if t<1:
        return 0
    if t==1:
        return 1
    if t==2:
        return 2
    a,b=1,2
    for i in range(2,t):
        sums=a+b
        a=b
        b=sums
    return sums
N=int(input())
for i in range(N):
    a,b=map(int,input().split())
    print(methods(a,b))

二、背包问题

这类问题细分为0-1背包问题和完全背包问题,具体差别就在于物品是否有无穷个。

通项公式:f(i,j)=max(f(i-1,j),f(i-1(或i),j-w(i))+v(i)) 

def f(n,m,v,w):
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if j<v[i-1]:
                dp[i][j]=dp[i-1][j]
            else:         #0-1背包(完全背包)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]](或dp[i][j-w[i-1]])+v[i-1])
    return dp

举例说明 

0-1背包问题 

假设有一个承重力量为C的背包。现有n件物品,质量分别为w1,w2,……,wn,价值分别为v1,v2,……vn,求让背包里装入的物品具有最大价值总和的物品子集。

【问题描述】

假设周末学校要组织跳蚤市场,某学生准备了电子词典、篮球、网球拍和考研书4件物品进行交易,要用自己的书包把这些物品带到学校。各个物品的质量w和价值v如表所示,该学生书包的最大承重量C=8。我们要解决的问题是帮助该同学找到最合理的搭配方案,使他能用书包带到学校的物品价值最大。

电子词典 篮球 网球拍 单词书

2 4 5 3

5 4 6 2

【输入样例】

【输出样例】

一行,表示最优方案的物品

【样例输入】

【样例输出】

1 3

n=4
c=8
w=[2,4,5,3]
v=[5,4,6,2]
def bag(n,c,w,v):
    results=[[0 for i in range(c+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,c+1):
            if j<w[i-1]:
                results[i][j]=results[i-1][j]
            else:  #在这里最多只能取一个物品,所以取了当前物品后需要返回上一层
                results[i][j]=max(results[i-1][j],results[i-1][j-w[i-1]]+v[i-1])
    return results
res=bag(n,c,w,v)
def rec(n,c,w,res):
    x=[0 for i in range(n+1)]
    j=c
    i=n
    while i>=0:
        if res[i][j]>res[i-1][j]:
            x[i]=1
            j=j-w[i]
        i=i-1
    for i in range(1+n):
        if x[i]==1:
            print(i,end=' ')
rec(n,c,w,res)

完全背包问题 

【问题描述】

对于吃货来说,过年最幸福的事就是吃了,没有之一!

但是对于女生来说,卡路里(热量)是天敌啊!

资深美女湫湫深谙“胖来如山倒,胖去如抽丝”的道理,所以她希望你能帮忙制定一个食谱,能使她吃得开心的同时,不会制造太多的天敌。

当然,为了方便你制作食谱,湫湫给了你每日食物清单,上面描述了当天她想吃的每种食物能带给她的幸福程度,以及会增加的卡路里量。

【输入形式】

输入包含多组测试用例。

每组数据以一个整数n开始,表示每天的食物清单有n种食物。

接下来n行,每行两个整数a和b,其中a表示这种食物可以带给湫湫的幸福值(数值越大,越幸福),b表示湫湫吃这种食物会吸收的卡路里量。

最后是一个整数m,表示湫湫一天吸收的卡路里不能超过m。

【输出形式】

对每份清单,输出一个整数,即满足卡路里吸收量的同时,湫湫可获得的最大幸福值。

【样例输入】

3

3 3

7 7

9 9

10

5

1 1

5 3

10 3

6 8

7 5

6

【样例输出】

10

20

while(1):
    def bag(n,m,Happiness,Calorie):
        results=[[0 for i in range(m+1)] for j in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                if j<Calorie[i-1]:
                    results[i][j]=results[i-1][j]
                else:     #因为物品无穷个,所有选完后需要在当前层继续选,不用返回上一层
                    results[i][j]=max(results[i-1][j],results[i][j-Calorie[i-1]]+Happiness[i-1])
        return results
    n=int(input())
    Happiness=[]
    Calorie=[]
    for i in range(n):
        a,b=map(int,input().split())
        Happiness.append(a)
        Calorie.append(b)
    m=int(input())
    res=bag(n,m,Happiness,Calorie)
    print(res[-1][-1])

矿工问题

【问题描述】

假设某地区有5座钻石矿,每座钻石矿的钻石储量不同,根据挖矿难度,需要参与挖掘的工人数量也不同。假设能够参与挖矿工人的总数是10人,且每座钻石矿要么全挖,要么不挖,不能只派出一部分人挖取一部分矿产。要求用程序求解出,要想得到尽可能多的钻石,应该选择挖取哪几座矿产?

矿产编号 钻石储量 所需工人数量

1 400 5

2 500 5

3 200 3

4 300 4

5 350 3

【输入形式】

【输出形式】

一行,表示获得的最大矿产数

【样例输入】

【样例输出】

900

G=[400,500,200,300,350]
L=[5,5,3,4,3]
def goldMine(n,m,G,L):
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if j<L[i-1]:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-L[i-1]]+G[i-1])
    return dp
lst=goldMine(5,10,G,L)
print(lst[-1][-1])

三、最长递增子列

这个式子主要是求最长递增子列的长度,而事实上我们还需要求得最长递增子列的元素。 

通项公式:f(i,j)=max(f(i),f(j)+1)

def f(arr):
    dp=[1]*len(arr)
    for i in range(len(arr)):
        for j in range(i):
            if arr[j]<arr[i]:          
                dp[i]=max(dp[i],dp[j]+1)      #状态转移函数
    return dp

举例说明 

最长递增子序列

【问题描述】

最长递增子序列问题即给定一个序列,求解其中最长的递增子序列的长度问题。

先给定序列A{3,1,4,5,9,2,6,5,0},求其最长递增子序列。

【输入样例】

一行,输入A

【输出样例】

一行,最长递增子序列

【样例输入】

3 1 4 5 9 2 6 5 0

【样例输出】

1 4 5 9

def getdp1(arr):    #求得最长递增子列的长度
    n=len(arr)
    dp=[0 for i in range(n)]
    for i in range(n):
        dp[i]=1
        for j in range(i):
            if arr[i]>arr[j]:
                dp[i]=max(dp[i],dp[j]+1)     #动态规划
    return dp
def generateLST(arr):     #求得最长递增子列的元素
    dp=getdp1(arr)
    n=max(dp)
    index=dp.index(n)
    lis=[0]*n
    n-=1
    lis[n]=arr[index]
    for i in range(index-1,-1,-1):
        if arr[i]<arr[index] and dp[i]==dp[index]-1:
            n-=1
            lis[n]=arr[i]
            index=i
    return lis
arr=[3,1,4,5,9,2,6,5,0]
for i in generateLST(arr):
    print(i,end=' ')

最少拦截系统 

【问题描述】

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

【输入形式】

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

【输出形式】

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

【样例输入】

8 389 207 155 300 299 170 158 65

【样例输出】

2

def getdp(arr):                          #得到每个元素的最长递减序列
    n=len(arr)                         
    dp=[1]*n                             #每个元素的最长递减序列初始化都是1
    for i in range(n):                   
        for j in range(i):                     
            if arr[i]<arr[j]:            #从第一个元素一直到当前元素,找比当前元素大的
                dp[i]=max(dp[i],dp[j]+1)   #找到后,动态规划,找到最大的长度
    return dp                            #最后得到的是每个元素的最大递减子序列长度
def generateLST(arr):                    #获取最大递减子序列的元素
    dp=getdp(arr)                       
    n=max(dp)
    index=dp.index(n)
    lst=[0]*n                            #初始化结果列表
    n-=1
    lst[n]=arr[index]                    #最后一个值容易得到
    for i in range(index-1,-1,-1):      #从后往前遍历
        #当找到比当前元素大并且该元素的最大递减子序列长度比当前元素的最大递减子序列长度小1时
        if arr[i]>arr[index] and dp[i]==dp[index]-1:      
            lst[n]=arr[i]    #该元素就是一个结果,加入结果列表中
            index=i          #更新当前元素
            n-=1             
    return lst
while(1):
    arr=[int(i) for i in input().split()]   
    arr.pop(0)
    sums=0
    while arr:
        sums+=1
        res=generateLST(arr)       #每次找到最大递减子序列,这些都可以用一个导弹拦截系统拦截
        for i in res:             #拦截完就从列表中删除,一直删除直到列表中没有导弹了,得到的就是最小的拦截系统数
            arr.remove(i)
    print(sums)

文章目录

序号 文章目录 直达链接
1 简单排序 https://want595.blog.csdn.net/article/details/128478423
2 高级排序 https://want595.blog.csdn.net/article/details/128498290
3 查找算法 https://want595.blog.csdn.net/article/details/128518434
4 哈希算法 https://want595.blog.csdn.net/article/details/128642705
5 二叉树 https://want595.blog.csdn.net/article/details/128546386
6 单链表 https://want595.blog.csdn.net/article/details/128549471
7 广度优先搜索 https://want595.blog.csdn.net/article/details/128562776
8 深度优先搜索 https://want595.blog.csdn.net/article/details/128688457
9 回溯法 https://want595.blog.csdn.net/article/details/128620465
10 分治算法 https://want595.blog.csdn.net/article/details/128791210
11 动态规划 https://want595.blog.csdn.net/article/details/128788989

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

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

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

相关文章

  • 【动态规划】背包问题题型及方法归纳

    背包问题是在规定背包容量为j的前提下,每个物品对应的体积为v[i],价值为w[i],从物品0到物品i中选择物品放入背包中, 找出符合某种要求的价值 。 (1)背包问题种类 01背包:每种物品只能选择1个。 完全背包:每种物品可以选择无限个。 多重背包:每种物品最多可选

    2024年02月02日
    浏览(40)
  • 【LeetCode动态规划#12】详解买卖股票I~IV,经典dp题型

    力扣题目链接(opens new window) 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最

    2023年04月24日
    浏览(53)
  • 【第二十五课】动态规划:完全背包问题(acwing-3 / 公式推导 / 思路理解 / 优化 / c++代码)

    目录 思路 朴素代码 优化 公式推导上  二维代码  一维代码 公式理解上   在开始看完全背包问题之前,可能需要先了解01背包及其解决办法。 指路👇 【第二十五课】动态规划:01背包问题(acwing-2 / 思路 / 含一维数组优化 / c++代码) 这个问题和01背包的区别就是 每件物品可以

    2024年03月19日
    浏览(62)
  • Midjourney的万能套用公式&疑难杂症

    哈喽,大家好,我是木易巷! 昨天给大家出了一期【Midjourney保姆级注册使用教程】,错过的小伙伴可以先去点击查看一下:【AI作图】Midjourney保姆级注册使用教程 今天,木易巷介绍一下关于Midjourney的使用技巧疑难杂症,让大家更好的使用Midjourney,并解答一下大家的疑惑,请

    2024年02月06日
    浏览(43)
  • AIGC ChatGPT 4 Prompt 万能提示词公式

    最近大家都在使用ChatGPT来帮助自己完成相应的工作。很多时候大家提出的问题 得不到很清晰,很明确的答案 。 我们应该怎么样来和ChatGPT进行有效的沟通呢? 例如我们先来问一问ChatGPT: 要获得最准确的回复,请确保遵循以下建议: 明确性 :请尽量明确描述您的问题。确保

    2024年01月21日
    浏览(86)
  • 有趣工具合集小程序-做你的小树洞小程序

    今天闲来无事,发现了一个有趣的小程序- 做你的小树洞 ,包含ChatGpt小机器人、抛硬币、手持弹幕、亲戚计算器、藏头诗、唐诗三百首、歇后语以及猜谜语等功能 小程序总体界面是这样的 1.藏头诗 这个小程序里边有很多有趣的小功能,里边包含了 藏头诗 的创作,包含了一

    2024年02月13日
    浏览(36)
  • Data-Copilot: 大语言模型做你最贴心省事的数据助手

    Data-Copilot: Bridging Billions of Data and Humans with Autonomous Workflow 无需繁琐操作,只需要输入一句话, Data-Copilot自动帮你完成查数据,分析数据,管理数据,预测趋势,还可以画图做表 论文链接: 论文地址 Data-Copilot: arxiv Repo: github 欢迎来github讨论交流,喜欢的话记得star哦 Demo: Demo in space 金

    2024年02月09日
    浏览(27)
  • 想做邮件营销,哪个平台好用?

    邮件营销作为传统的营销方式之一,市场上已经出现了很多相关的邮件营销工具。但是,市场的筛选为大家留下了真正好用的邮件营销平台。今天,我们就来介绍一下受到众多好评的, 市场上优秀的邮件营销平台 ——Zoho Campaigns。 一、产品背景 Zoho Campaigns是Zoho公司开发的一

    2024年02月11日
    浏览(35)
  • 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 )

    动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ; 具体的算法都有具体的步骤 , 如 : 二分法 , 其 有固定的解决步骤 , 先取一个中心点 , 判断解在左边还是右边 , 然后在一边再取一个中心点 , 再进行判定 , 该算法有具体的步骤 ; 动态规划

    2024年01月16日
    浏览(45)
  • 动态规划:什么是动态规划?

    动态规划(Dynamic Programming,简称Dp) 是 一种算法思想 : 将原(大)问题化解成子问题,再根据子问题的解得出原问题的解; 状态转移方程 :是一种组合关系,描述了一种原问题与子问题的组合关系 PS: 看着描述和最优子结构问题的描述一样,其实就是一样,一个是文字描述,

    2024年02月08日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包