python算法与数据结构---动态规划

动态规划

记不住过去的人,注定要重蹈覆辙。

定义

对于一个模型为n的问题,将其分解为k个规模较小的子问题(阶段),按顺序求解子问题,前一子问题的解,为后一子问题提供有用的信息。在求解任一子问题时,通过决策求得局部最优解,依次解决各子问题。最后通过简单的判断,得到原问题的解。

经典案例—斐波那契数列

斐波那契数列又称黄金分割数列。因数学家莱昂纳多-斐波那契以兔子繁殖为例引入,故又称兔子数列。

1, 1, 2, 3, 5, 8, 13, 21...

在数学上满足递推的方法定义:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (n>=2)
def fib(n):if n <= 0:return 0if n == 1:return 1return fib(n-1) + fib(n-2)

在这里插入图片描述
分析:
上图中的二叉树的每个子节点都需要执行一次,如果n= 6,则需要再向下延申,fib(2)就需要执行5次。每次调用时都需要保留上下文,在时间和空间上开销很大。那如果我们把每次计算的结果保存起来,下次用到的时候直接通过查表得方式调用,就可以节省大量得时间,这就是动态规划得基本思想。

动态规划解决

def fib_dp(n):#定义一个dp数组,记录每个n的值,这里n+1长度的便于写代码dp = [-1] * (n+1)#初始化dp[1] = dp[2] = 1for i in range(3, n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

解题步骤

核心思想是递推,难点在于dp[i]状态代表什么,然后构造转移矩阵,利用初始条件递推出最终结果。
解题步骤:

  1. 划分阶段:按照问题的时间和空间特征,把若干问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要有序或者是可排序的,否则问题就无法求解。
  2. 确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
  3. 确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就根据上一阶段的状态和决策来导出本阶段的状态。所以确定了决策,状态转移方程也就可写出。但事实上常常是反过来的,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
  4. 寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

动态规划算法的性质

动态规划的要素:问题的最优解由相关子问题的最优解组合而成,并且可以独立求解子问题(最优子结构)。

  • (1)最优化原理:如果问题的最优解包含的子问题也是最优的,就称该问题具有最优子结构,即满足最优化原理;
  • (2)无后效性:即某阶段状态(定义的新子问题)一旦确定,就不受这个状态以后决策的影响,也就是说,某状态以后的过程不会影响以前的状态,只与其以前的状态有关。

LeetCode例题

62不同路径

https://leetcode.cn/problems/unique-paths/description/
在这里插入图片描述
思路:
每一步只能从向下或向右移动一步,所以对于坐标(i,j)要么从(i-1,j)过来(向下走一步),要么从(i,j-1)过来(向右走一步)。

状态定义:
dp(i, j)表示从左上角走到(i,j)的路径数量

class Solution:def uniquePaths(self, m: int, n: int) -> int:#定义dp数组,用dp(i,j)表示从左上角走到(i,j)的路径数量dp(i,j)dp = [[0] * n for _ in range(m)]# 初始化dp数组,第一行和第一列、应该都是1,都只有一种情况,从左边或者上边过来dp[0][0] = 1for i in range(m):dp[i][0] = 1for j in range(n):dp[0][j] = 1#print(dp) # 可以看下dp  [[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0]]#计算剩余位置,填充好dp数组for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i-1][j] + dp[i][j-1]print(dp)  # [[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]]## 通过查表的方式,返回最终结果return dp[m-1][n-1]

LCR 099. 最小路径和

https://leetcode.cn/problems/0i0mDW/description/
在这里插入图片描述
思路:
与上一题类似,对于坐标(i,j)要么从(i-1,j)过来(向下走一步),要么从(i,j-1)过来(向右走一步),但是加了条件,每个坐标上的值有了意义,需要进行累加处理。

状态:

设dp为大小m*n的矩阵,其中dp(i,j)的值代表直到走到(i,j)的最小路径和。

转移方程:

  1. 当可以从左边和上面过来,即左边和上边都不是矩阵边界时:
    dp(i, j) = grid(i, j) + min(dp(i-1, j), dp(i, j-1))
    
  2. 当只能从上边过来,即左边是矩阵边界时:
    dp(i, j) = grid(i, j ) + dp(i, j-1)
    
  3. 当只能从左边过来,即上边是矩阵边界时(i=0)
    dp(i, j) = grid(i, j) + dp(i, j-1)
    
  4. 在起点时(i=0, j=0)
    dp(i, j) = grid(i, j)
    
class Solution:def minPathSum(self, grid: List[List[int]]) -> int:rows = len(grid)cols = len(grid[0])#其中dp(i, j)的值代表直到走到(i,j)的最小路径和dp = [[0] * cols for _ in range(rows)]for i in range(rows):for j in range(cols):#起点if i == 0 and j == 0:dp[i][j] = grid[i][j]# 中间的点,可以从左边和上边过来elif i != 0 and j != 0:dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])#只能从左边过来elif i == 0 and j != 0:dp[i][j] = grid[i][j] + dp[i][j-1]#只能从上边过来elif i != 0 and j == 0:dp[i][j] = grid[i][j] + dp[i-1][j]#print(dp) # grid =[[1,3,1],[1,5,1],[4,2,1]]return dp[rows-1][cols-1]

1884. 鸡蛋掉落-两枚鸡蛋

https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/description/
在这里插入图片描述
思路:

开始有两枚鸡蛋,所以要分情况讨论,还剩两枚鸡蛋,和一枚鸡蛋;

  • 1、如果只有一枚鸡蛋:此时我们需要从1层逐层校验,才能获得确切的值,
  • 2、如果有两枚鸡蛋:第一次操作可以在任意一层,如果在k层丢下时碎了一个,那问题就转换成了第一点。

状态:

dp(i, j)表示有 i+1 鸡蛋时,验证 j 层楼需要的最少操作次数,我们可以分开分析 i = 0 和 i = 1的情况:

  • ·i = 0 时(只有一枚鸡蛋了):
    需要逐层检验,当在 j 层楼时,则dp(0, j) = j

  • i = 1时:

    • (1)假设当前在k层的时候第一枚鸡蛋碎了,那么问题就转换成了dp(0, k-1),总共的操作次数是,dp(0, k-1) + 1;

    • (2)如果当前在k层丢下鸡蛋,没有碎,此时可以证明在k层的时候鸡蛋不会碎,那么问题就转化成dp(1, j-k),总共的操作次数是dp(1, j-k) + 1

    • 基于(1)(2)取最坏情况:

      max(dp(0, k-1), dp(1, j-k) + 1)

    • 综上,

      dp(1, j) = min(dp(1, j), max(dp(0, k-1), dp(1, j-k) + 1))

转移方程:

dp(0, j) = j, i=0
dp(1, j) = min(dp(1, j), max(dp(1, j), max(dp(0, k-1), dp(1, j-k) + 1))), i=1

class Solution:def twoEggDrop(self, n: int) -> int:# dp(i, j)表示有i+1枚鸡蛋时,验证j层楼需要的最少操作次数dp = [[sys.maxsize] * (n + 1) for _ in range(2)]#初始化dp数组dp[0][0] = dp[1][0] = 0 #初始化,只有一枚鸡蛋的情况for j in range(n+1):dp[0][j] = jfor j in range(n+1):#两枚鸡蛋时,在k层是否碎了,分情况讨论for k in range(j + 1):dp[1][j] = min(dp[1][j], max(dp[0][k-1] + 1, dp[1][j-k] + 1))# 查表返回最终结果return dp[1][n]

附录基础

python数据结构与算法理论基础(专栏)

数据结构与算法(python)http://t.csdnimg.cn/Gb6MN

程序 = 数据结构 + 算法;而且在面试过程中这些是必考,必问的内容。内容大纲:基础数据结构(树、链表、栈、队列等)、常见算法(排序算法、递归算法等)。

专栏是基于python的基础知识,是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念,同时结合力扣题目,也能更好的掌握这些知识,达到在面试中游刃有余的效果。

python基础语法

python基础精讲 http://t.csdnimg.cn/HdKdi

本专栏主要针对python基础语法,帮助学习者快速接触并掌握python大部分最重要的语法特征。
1、基本数据类型和变量
2、分支结构与循环结构
3、函数与异常处理
4、类与模块
5、文件读写
通过本专栏可以快速掌握python的基础语法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/251970.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

无向图-树的重心-DFS求解

思路&#xff1a; 本题的本质是树的dfs&#xff0c; 每次dfs可以确定以u为重心的最大连通块的节点数&#xff0c;并且更新一下ans。 也就是说&#xff0c;dfs并不直接返回答案&#xff0c;而是在每次更新中迭代一次答案。 这样的套路会经常用到&#xff0c;在 树的dfs 题目中…

yarn/npm certificate has expired

目录 报错 原因&#xff1a;HTTPS 证书验证失败 方法 a.检查网络安全软件&#xff1a;可能会拦截或修改 HTTPS 流量 b.strict-ssl:false关闭验证【临时方法】 报错 info No lockfile found. [1/4] Resolving packages... error Error: certificate has expired at TLS…

如何发布自己的npm包:

1.创建一个打包组件或者库&#xff1a; 安装weback&#xff1a; 打开项目&#xff1a; 创建webpack.config.js,创建src目录 打包好了后发现两个js文件都被压缩了&#xff0c;我们想开发使用未压缩&#xff0c;生产使用压缩文件。 erserPlugin&#xff1a;&#xff08;推荐使用…

二叉搜索树题目:二叉搜索树的最近公共祖先

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;二叉搜索树的最近公共祖先 出处&#xff1a;235. 二叉搜索树的最近公共祖先 难度 3 级 题目描述 要求 给定一个…

机器学习中的有监督学习和无监督学习

有监督学习 简单来说&#xff0c;就是人教会计算机学会做一件事。 给算法一个数据集&#xff0c;其中数据集中包含了正确答案&#xff0c;根据这个数据集&#xff0c;可以对额外的数据希望得到一个正确判断&#xff08;详见下面的例子&#xff09; 回归问题 例如现在有一个…

数模.matlab画图

一、mesh函数 上图是平常用到的方式 例题&#xff1a; 上图的meshgrid函数相当于上上图的前三个指令&#xff08;temp&#xff0c;x,y&#xff09; mash函数&#xff1a; mashc函数&#xff1a; mashz函数&#xff1a; 上图subplot函数的作用是将下标为index的图片放到对应的x&…

[技术杂谈]如何下载vscode历史版本

网站模板&#xff1a; https://code.visualstudio.com/updates/v1_85 如果你想下载1.84系列可以访问https://code.visualstudio.com/updates/v1_84​​​​​​ 然后看到&#xff1a; 选择对应版本下载即可&#xff0c;我是windows x64系统选择x64即可开始下载

C++杂选

#include <iostream> #include <regex>using namespace std;int main() { //它声明了一个 string 类型的变量 input&#xff0c;用于存储输入的字符串。然后使用 getline() 函数从标准输入中读取一行输入&#xff0c;并将其存储在 input 变量中。string input;getl…

Linux openKylin(开放麒麟)系统SSH服务安装配置与公网远程连接

文章目录 前言1. 安装SSH服务2. 本地SSH连接测试3. openKylin安装Cpolar4. 配置 SSH公网地址5. 公网远程SSH连接6. 固定SSH公网地址7. SSH固定地址连接8. 结语 前言 openKylin是中国首个基于Linux 的桌面操作系统开发者平台&#xff0c;通过开放操作系统源代码的方式&#xff…

pwn学习笔记(2)

pwn学习笔记&#xff08;2&#xff09; 1.三种常见的寄存器&#xff1a; ​ ax寄存器&#xff1a;通用寄存器&#xff0c;可用于存放多种数据 ​ bp寄存器&#xff1a;存放的是栈帧的栈底地址 ​ sp寄存器&#xff1a;存放的是栈顶的地址 2.栈帧与栈工作的简介&#xff1a…

【机器学习】基于集成学习的 Amazon 用户评论质量预测

实验六: 基于集成学习的 Amazon 用户评论质量预测 1 案例简介 ​ 随着电商平台的兴起&#xff0c;以及疫情的持续影响&#xff0c;线上购物在我们的日常生活中扮演着越来越重要的角色。在进行线上商品挑选时&#xff0c;评论往往是我们十分关注的一个方面。然而目前电商网站的…

vue前端+nodejs后端通信-简单demo

本文记录vue前端nodejs后端通讯最简单的方法&#xff0c;供广大网友最快速进入全栈开发。 技术架构 前端 vue axios 后端 nodejs express 一、前端部分-搭建VUE 项目 vue create Vnodenpm run serve 启动&#xff1b; 具体操作步骤&#xff0c;请自行百度&#xff0c;这里没…

ArcGIS学习(三)数据可视化

ArcGIS学习(三)数据可视化 1.矢量数据可视化 需要提前说明的是,在ArcGIS中,所有的可视化选项设置都是在“图层属性”对话框里面的“符号系统”中实现的。 对于矢量数据的可视化,主要有四种可视化方式: 按“要素”可视化按“类别”可视化按“数量”可视化按“图表”可视…

25.云原生ArgoCD高级之app of apps模式

文章目录 app of apps 模式介绍app如何管理apphelm方式管理kustomize方式管理 app of apps 模式介绍 通过一个app来管理其他app&#xff0c;当有多个项目要发布创建多个app比较麻烦&#xff0c;此时可以创建一个管理app&#xff0c;管理app创建后会创建其他app。比较适合项目环…

Linux--- vim详解

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 “学如逆水行舟&#xff0…

EF Core 的基本使用及常见的坑

EF Core 的基本使用及常见的坑 1. EF Core 是什么 简单来说&#xff0c;就是实现代码中的类到数据库中表的映射的一种方法。 宝啊&#xff0c;是不是觉得我才开篇就鬼话连篇。 举个例子&#xff0c;假设我们要创建一个名为employees的表&#xff0c;包含id、name、age和salar…

vue实现瀑布流

每个色块宽度一致&#xff0c;高度自适应 <!DOCTYPE html> <html><head><meta charset"utf-8"><meta http-equiv"X-UA-Compatible" content"IEedge,chrome1"><meta name"renderer" content"we…

STM32F407移植OpenHarmony笔记7

继上一篇笔记&#xff0c;成功启动了liteos_m内核&#xff0c;可以创建线程了&#xff0c;也能看到shell控制台了。 今天研究文件系统&#xff0c;让控制台相关文件命令如mkdir和ls能工作。 liteos_m内核支持fatfs和littlefs两个文件系统&#xff0c; fatfs适用于SD卡&#xff…

【C++】C++入门 — 类和对象初步介绍

类和对象 1 类的作用域2 类的实例化3 类对象模型4 this指针介绍&#xff1a;特性&#xff1a; Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;下一篇文章见&#xff01;&#xff01;&#xff01; 1 类的作用域 类定义了一个新的作用域&#xff0c;类的…

指针的深入理解(四)

这节主要讨论sizeof和strlen的区别&#xff0c;以及一些理解题。 sizeof 求的是对象的大小&#xff0c;深入理解一点就是&#xff1a;这个对象&#xff0c;他一定有一块对应的内存空间。求的就是这一块内存空间。 strlen 只能用来求字符串&#xff0c; 求取的是字符串的长度。…