蓝桥杯动态规划基础篇(一)

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

一、什么是动态规划?有套路吗?

动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

用简单通俗的话来说:对于一个原问题,我们把这一个原问题拆分成多个子问题,直到子问题可以直接解决,再把子问题答案保存起来,以减少重复计算,使用子问题答案反推,得出原问题解。

动态规划的实现步骤:

  1. 确定是否为动态规划问题:是否可以把这个问题分解成可以求解的子问题
  2. 找关系:分解后的子问题之间有什么联系?确定原问题的子问题数量也很重要
  3. 表达递归关系:不要着急写代码,在写代码之前清楚地表达递归关系可以加强你对问题的理解并使过程高效
  4. 决定解决问题的迭代或递归方法:递归更好
  5. 添加记忆:记忆是存储子问题的结果并在需要解决类似的子问题时再次调用它们的过程。这将降低问题的时间复杂度。如果我们不使用记忆,类似的子问题会重复解决,这可能导致指数时间复杂度。
  6. 实现

二、动态规划的特征

重要的是要知道何时应用动态规划算法,让我们了解动态问题的 2 个特征

  1. 最优子结构:如果一个问题的最优解包含子问题的最优解,则该问题是最优子结构。只有满足最优子结构,才能用动态规划的方法求解。如果问题具有最优子结构,我们可以递归求最优解。此外,如果问题没有最佳解决方案,则没有定义递归算法的基础,也是不能使用动态规划方法求解。
  2. 重叠子问题:如果递归算法重复访问相同的子问题,则该问题称为重叠子问题。如果任何问题都有重叠的子问题(公共子子问题),那么我们可以通过只计算一次来改进子问题的重复实现。如果问题没有重叠的子问题,那么使用动态规划算法来解决问题是不可行的。
    画个图说明:
    蓝桥杯动态规划基础篇(一)

三、动态规划三元素

正如上面所了解的,动态规划是将问题划分为各种子问题以找出最佳解决方案的算法。在使用动态规划方法解决问题陈述时,将问题总共分为3个元素以获得最终结果。这些元素是:

  1. 子结构: 子结构是将给定的问题陈述划分为更小的子问题的过程。在这里,我们设法根据子问题的解决方案来确定原始问题的解决方案。
  2. 表结构:子问题的解决方案需要解决后存储到一个表中。这很重要,因为我们知道,动态编程会多次重用子问题的解决方案,这样我们就不必一次又一次地重复解决同一个问题。
  3. 自下而上的方法:使用表格组合子问题的解决方案以达到最终结果的过程。该过程从解决最小的子问题开始,然后将它们的解决方案与不断增加的子问题结合起来,直到获得原始问题的最终解决方案。

四、生活中的动态规划

想象一下,你想去几条街外的一家新杂货店,但你不知道怎么去那里,这是你就有多条测试的路线,要解决通往商店的路线的子问题,您可以在智能手机的地图上查找路线,然后前往那里。如果您以递归方式思考,那么每次您想去商店时,你都必须花时间再次查找路线。取而代之的是,我们自然而然地动态思考,从我们第一次查找商店时就记住了去往商店的方向,因此我们以后去的时候就不需要花时间去查找它们了。

五、斐波那契数列

5.1 问题

斐波那契数基本规律:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

斐波那契数列 Fn 由递归关系定义:

F n = F n-1 + F n-2

在python中递归基本方法:

def r_fibo(n): 
   if n <= 1: 
       return n 
   else: 
       return(r_fibo(n-1) + r_fibo(n-2))

在这里,程序将一次又一次地调用自己来计算更多的值。基于递归的方法的时间复杂度的计算在 O(2​^N) 左右。这种方法的空间复杂度是 O(N),因为递归可以最大到 N。

例如:给定一个数字 n,打印第 n 个斐波那契数。
输入输出例子:

输入:n = 2
输出:1

输入:n = 9
输出:34

5.2 递归解决

思考:该数列的基本规律是求的那个数是左边两个数之和,可以总是看成两个数之和,我们在这里设置n表示第几个数,设置start表示第一个是,last表示第二个数。

实现如下:

#0,1,1,2,3,5.....
def fib(n, start, last):
    # 如果是第一个数,直接返回
    if n-1 == 0:
        return start
    # 如果n大于1
    else:
        new_last = start + last  #第二个数向右移动一个,j就要前两个数相加
        start = last # 第二个数就变成第一个数
        return fib(n-1, start, new_last)  # 继续调用


if __name__ == "__main__":
    #开始两个数设置为01
    print(fibonacci(10, 0, 1))

现在调用了 n 次递归函数。例如计算第 5 项的斐波那契数列,递归的原始树:

                          fib(5)    
                     / \ 
               fib(4) fib(3)    
             / \ / \ 
         fib(3) fib(2) fib(2) fib(1) 
        / \ / \ / \ 
  fib(2) fib(1) fib( 1) fib(0) fib(1) fib(0) 
  / \ 
fib(1) fib(0)

递归如下:

    fib(5) 

    fib(4)

    fib(3)

    fib(2)

    fib(1)

如果用C语言实现也很简答,思路一样:

// 0,1,1,2,3,5,.....
#include<stdio.h>
int fib(int n)
{
if (n <= 1)
	return n;
return fib(n-1) + fib(n-2);
}

int main ()
{
int n = 9;
printf("%d", fib(n));
return 0;
}

5.3 动态规划

我们可以通过存储到目前为止计算的斐波那契数来避免递归方法中的重复工作。

python版:这里我们主要是使用列表来存储值

# 0.1.1.2.3.5

def fib(n):
    # 初始两个数,列表用来存储
    f = [0, 1]
    # range包左不包右
    for i in range(2, n+1):
        f.append(f[i-1] + f[i-2]) # 添加前两个胡的和
    return f[n]

print(fib(9))

C语言实现:

// 0,1,1,2,3,5,.....

#include<stdio.h>
int fib(int n)
{
// C语言中的数组就是我们python中的列表,等效 ,用它来存储结果 
int f[n+2];  //  01已经占了两个位置,我们计算后面的位置 
int i;

// 数组前两个值固定为01 
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++)
{
  // 例如:f[2]=f[1]+f[0]
	f[i] = f[i-1] + f[i-2];
}

return f[n]; //索引返回第n个值 
}

int main ()
{
int n = 9;
printf("%d", fib(n));
return 0;
}

六、加泰罗尼亚数列

6.1 问题

加泰罗尼亚数规律:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862…
加泰罗尼亚数满足以下递归公式:
蓝桥杯动态规划基础篇(一)

问题:求前n项的加泰罗尼亚数

6.2 归实现

直接套公式,前提你能看得懂这公式,它就是最基本的累加公式,大学生肯定看得懂吧?

python实现如下:

def catalan(n):
    # 只有一个情况
    if n <= 1:
        return 1
 
    # 根据公式:累加求和
    # 递归:catalan(i)*catalan(n-i-1)
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)
 
    return res
 
n=int(input('请输入n的值:'))
for i in range(n):
    print (catalan(i),end=" ")

6.3 动态规划

上面的递归实现做了很多重复的工作,由于存在重叠的子问题,我们可以为此使用动态规划。

实现如下:

def catalan(n):
    # 前两个值情况
    if (n == 0 or n == 1):
        return 1
 
    # 存储子问题结果的表,开始为全0
    catalan =[0]*(n+1)
 
    # 初始化前两个值
    catalan[0] = 1
    catalan[1] = 1
 
   # 把值覆盖进去
    for i in range(2, n + 1):
        for j in range(i):
            catalan[i] += catalan[j]* catalan[i-j-1]
 
    # 返回值
    return catalan[n]
 
n=int(input('请输入n:'))

for i in range(n):
    print(catalan(i), end=" ")

七、二项式系数

基本定义这是你在大学应该学过的,基本定义:
蓝桥杯动态规划基础篇(一)

二项式系数的对称特性:
蓝桥杯动态规划基础篇(一)
帕斯卡法则是一重要的递归等式:
蓝桥杯动态规划基础篇(一)
基础问题我是不应该提到的,但是便于讲解,还是拿出来,因为这应该是大学生必备知识、

7.1 计算二项式的数学方法

递归公式:
蓝桥杯动态规划基础篇(一)
其中特别指定:
蓝桥杯动态规划基础篇(一)
阶乘公式,二项式系数最简洁的表达式是阶乘:
蓝桥杯动态规划基础篇(一)

7.2 问题

接受两个参数 n 和 k,并返回二项式系数 C(n, k) 二项式系数值。例如,对于 n = 4 和 k = 2,函数应该返回 6,对于 n = 5 和 k = 2 ,它应该返回10。

7.3 递归求解

根据数学知识(上面说到的计算二项式中递归公式),递归为:

  C(n, k) = C(n-1, k-1) + C(n-1, k)
  C(n, 0) = C(n, n) = 1

使用python实现如下:

def er(n, k):
 
    if k > n:
        return 0
    if k == 0 or k == n:
        return 1
 
    # 继续调用
    return er(n-1, k-1) + er(n-1, k)
 
 

n = int(input('请输入n:'))
k = int(input('请输入k:'))
print ("C(%d,%d) = %d" % (n, k,er(n, k)))

运行例子:

请输入n:5
请输入k:2
C(5,2) = 10

C语言可以实现如下:

#include <stdio.h>
 
int er(int n, int k)
{
    // 基本情况 
    if (k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
 
    // 回调 
    return er(n - 1, k - 1)
           + er(n - 1, k);
}
 
// 主函数调用 
int main()
{
    int n, k ;
    printf("请输入n值:");
    scanf("%d",&n);

    printf("请输入k值:");
    scanf("%d",&k);

    printf("C(%d, %d) = %d ", n, k,
           er(n, k));
    return 0;
}

演示:
蓝桥杯动态规划基础篇(一)

7.3 动态规划求解

python实现如下:

def er(n, k):
    #初始化为0,把值存在列表
    C = [[0 for x in range(k+1)] for x in range(n+1)]
#     print(C)
 
    for i in range(n+1):
        for j in range(min(i, k)+1):
            # 基本情况
            if j == 0 or j == i:
                C[i][j] = 1
                
           # 调用
            else:
                C[i][j] = C[i-1][j-1] + C[i-1][j]
 # 返回n,k情况
    return C[n][k]
 
# 52就是五行三列
# n = 5
# k = 2
n=int(input('请输入n:'))
k=int(input('请输入k:'))
# print(er(n,k))
print(" C[" + str(n) + "][" + str(k) + "] = "+ str(er(n, k)))

C语言实现如下:

#include <stdio.h>
 
 // 最小值函数 
int min(int a, int b) { return (a < b) ? a : b; }

//返回二项式系数 C(n, k) 的值
int er(int n, int k)
{
    int C[n + 1][k + 1];
    int i, j;
    
// 计算二项式系数的值以自下而上的方式

    for (i = 0; i <= n; i++) {
        for (j = 0; j <= min(i, k); j++) {
            // 基本情况 
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // 存储值到数组 
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
 // 返回值 
    return C[n][k];
}
 

// 主函数 
int main()
{
    int n , k ;
    printf("请输入n:"); 
    scanf("%d",&n);
    printf("请输入k:"); 
    scanf("%d",&k);
    printf("C(%d, %d) = %d ", n, k,er(n, k));
    return 0;
}

演示:

蓝桥杯动态规划基础篇(一)

七、资料

可以到我的github仓库:计算机学习体系

如果你没有基础可看基础部分,数据结构没有基础看数据结构部分,如果你想直接做蓝桥杯真题,VIP题,蓝桥杯宝典,可以直接看蓝桥杯部分…应有尽有。

基础视频: b站

八、总结

你是否发现上面案例有相同之处?是否能总结出一个这种题型的代码模板?是否有固定的思考方式?请把你的思考记录下来,欢迎评论区回答你的思考,以便于大家交流。

加我vx拉你到蓝桥杯交流群:hxgsrubxjogxeeag文章来源地址https://www.toymoban.com/news/detail-438694.html

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

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

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

相关文章

  • 【蓝桥杯-筑基篇】动态规划

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 1.最大连续子段和 2.LCS 最大公共子序列 3.LIS 最长上升子序列 4.数塔 5.最大子矩阵和 6.背包问题 ①01背包问题 ②完全背包 这段代码是一个求最大子数组和的算法,使用的是动态规划的思想。下面是代码的解释: 首先定义了一个

    2023年04月24日
    浏览(73)
  • 蓝桥杯(路径 动态规划 C++)

     思路: 1、利用动态规划的思想。 2、用f[i]来记录从第一个点到第i个点的最短距离。 3、f[i]赋值分两种情况,第一种:f[i]为0的时候,也就是第一种刚到i点的情况,记录其距离为最小公倍数;第二种:f[i]已经有值了,比较新的点到其距离和之前点到其距离,取小的赋值。

    2024年02月07日
    浏览(38)
  • 【蓝桥杯/动态规划】数的计算

    题目描述 输入一个自然数 n (n≤1000)n (n leq 1000) n   ( n ≤ 1 0 0 0 ) ,我们对此自然数按照如下方法进行处理: 不作任何处理; 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 加上数后,继续按此规则进行处理,直到不能再加自然数为止。 问总共可以产生多少个数。

    2024年02月01日
    浏览(49)
  • 蓝桥杯-动态规划-子数组问题

    目录 一、乘积最大数组 二、乘积为正数的最长子数组长度 三、等差数列划分 四、最长湍流子数组 心得: 最重要的还是状态表示,我们需要根据题的意思,来分析出不同的题,不同的情况,来分析需要多少个状态 乘积最大数组 1.状态表示 dp[i]:到达i位置的最大乘积子数组。

    2024年02月05日
    浏览(36)
  • 蓝桥杯-回路计数(状态压缩、动态规划)

    蓝桥学院由 21 21 21 栋教学楼组成,教学楼编号 11 11 11 ​​ 到 21 21 21 ​​。对于两栋教学楼 a a a 和 b b b ​,当 a a a 和 b b b 互质时, a a a 和 b b b 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。 小蓝现在在第一栋教学楼,他想要访问每栋教学楼正

    2024年02月08日
    浏览(60)
  • 蓝桥:保险箱(Python,动态规划)

    小蓝有一个保险箱,保险箱上共有 n 位数字。小蓝可以任意调整保险箱上的每个数字,每一次操作可以将其中一位增加 1 或减少 1。当某位原本为 9 或 0 时可能会向前(左边)进位/退位,当最高位(左边第一位)上的数字变化时向前的进位或退位忽略。 例如: 00000 的第 5 位减

    2024年04月09日
    浏览(92)
  • JAVA蓝桥杯备考---6.动态规划(一)

    动态规划简称 DP,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 简单来说,动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决然后呢,把子问题答案保

    2024年02月19日
    浏览(33)
  • 动态规划树形DP课后习题蓝桥舞会

      蓝桥舞会 题目描述 蓝桥公司一共有n名员工,编号分别为1~n。 他们之间的关系就像一棵以董事长为根的树,父节点就是子节点的直接上司。每个员工有一个快乐指数aj。 现蓝桥董事会决定举办一场蓝桥舞会来让员工们在工作之余享受美好时光,不过对于每个员工,他们都

    2024年02月21日
    浏览(47)
  • 【蓝桥杯C/C++】专题六:动态规划

    在这里插入图片描述 本专题将讲解 最难理解 的算法之一:动态规划。介绍动态规划的基本概念、算法原理以及应用场景。首先,我们将介绍动态规划的定义和特点,以及它与递归、贪心算法的区别。接着,我们将详细介绍动态规划的解题思路和算法流程,包括状态转移方程

    2024年02月01日
    浏览(49)
  • 蓝桥杯:最优包含--动态规划(C语言)

    1、S串用i进行遍历,T串用j进行遍历。 2、dp数组[i][j]的含义:S串中从S[0]到S[i],最少修改dp[i][j]个字符,可以包含T串中从T[0]到T[j]这部分字符串。 3、遍历时遇到的情况有两种: (1)情况一:S[i]==T[j]        dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]);        dp[i-1][j]的含义:S[0]到S[i-1]中

    2024年02月16日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包