国外做网站被动收入,甘肃省崇信县门户网,建设项目环境影响登记表网站,网络推广方案找v信hyhyk1做推广好动态规划
记不住过去的人#xff0c;注定要重蹈覆辙。
定义
对于一个模型为n的问题#xff0c;将其分解为k个规模较小的子问题#xff08;阶段#xff09;#xff0c;按顺序求解子问题#xff0c;前一子问题的解#xff0c;为后一子问题提供有用的信息。在求解任一子…动态规划
记不住过去的人注定要重蹈覆辙。
定义
对于一个模型为n的问题将其分解为k个规模较小的子问题阶段按顺序求解子问题前一子问题的解为后一子问题提供有用的信息。在求解任一子问题时通过决策求得局部最优解依次解决各子问题。最后通过简单的判断得到原问题的解。
经典案例—斐波那契数列
斐波那契数列又称黄金分割数列。因数学家莱昂纳多-斐波那契以兔子繁殖为例引入故又称兔子数列。
1, 1, 2, 3, 5, 8, 13, 21...在数学上满足递推的方法定义
F(0) 0
F(1) 1
F(n) F(n-1) F(n-2) (n2)def fib(n):if n 0:return 0if n 1:return 1return fib(n-1) fib(n-2)分析 上图中的二叉树的每个子节点都需要执行一次如果n 6则需要再向下延申fib2就需要执行5次。每次调用时都需要保留上下文在时间和空间上开销很大。那如果我们把每次计算的结果保存起来下次用到的时候直接通过查表得方式调用就可以节省大量得时间这就是动态规划得基本思想。
动态规划解决
def fib_dp(n):#定义一个dp数组记录每个n的值这里n1长度的便于写代码dp [-1] * (n1)#初始化dp[1] dp[2] 1for i in range(3, n1):dp[i] dp[i-1] dp[i-2]return dp[n]解题步骤
核心思想是递推难点在于dp[i]状态代表什么然后构造转移矩阵利用初始条件递推出最终结果。 解题步骤
划分阶段按照问题的时间和空间特征把若干问题分为若干个阶段。在划分阶段时注意划分后的阶段一定要有序或者是可排序的否则问题就无法求解。确定状态和状态变量将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然状态的选择要满足无后效性。确定决策并写出状态转移方程因为决策和状态转移有着天然的联系状态转移就根据上一阶段的状态和决策来导出本阶段的状态。所以确定了决策状态转移方程也就可写出。但事实上常常是反过来的根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。寻找边界条件给出的状态转移方程是一个递推式需要一个递推的终止条件或边界条件。
动态规划算法的性质
动态规划的要素问题的最优解由相关子问题的最优解组合而成并且可以独立求解子问题最优子结构。
1最优化原理如果问题的最优解包含的子问题也是最优的就称该问题具有最优子结构即满足最优化原理2无后效性即某阶段状态定义的新子问题一旦确定就不受这个状态以后决策的影响也就是说某状态以后的过程不会影响以前的状态只与其以前的状态有关。
LeetCode例题
62不同路径
https://leetcode.cn/problems/unique-paths/description/ 思路 每一步只能从向下或向右移动一步所以对于坐标ij要么从i-1j过来向下走一步要么从ij-1过来向右走一步。
状态定义 dp(i, j)表示从左上角走到ij的路径数量
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/ 思路 与上一题类似对于坐标ij要么从i-1j过来向下走一步要么从ij-1过来向右走一步但是加了条件每个坐标上的值有了意义需要进行累加处理。
状态
设dp为大小m*n的矩阵其中dpij的值代表直到走到ij的最小路径和。
转移方程
当可以从左边和上面过来即左边和上边都不是矩阵边界时dp(i, j) grid(i, j) min(dp(i-1, j), dp(i, j-1))当只能从上边过来即左边是矩阵边界时dp(i, j) grid(i, j ) dp(i, j-1)当只能从左边过来即上边是矩阵边界时i0dp(i, j) grid(i, j) dp(i, j-1)在起点时(i0, j0)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)表示有 i1 鸡蛋时验证 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 基于12取最坏情况 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, i0 dp(1, j) min(dp(1, j), max(dp(1, j), max(dp(0, k-1), dp(1, j-k) 1))), i1 class Solution:def twoEggDrop(self, n: int) - int:# dp(i, j)表示有i1枚鸡蛋时验证j层楼需要的最少操作次数dp [[sys.maxsize] * (n 1) for _ in range(2)]#初始化dp数组dp[0][0] dp[1][0] 0 #初始化只有一枚鸡蛋的情况for j in range(n1):dp[0][j] jfor j in range(n1):#两枚鸡蛋时在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数据结构与算法理论基础专栏
数据结构与算法pythonhttp://t.csdnimg.cn/Gb6MN
程序 数据结构 算法而且在面试过程中这些是必考必问的内容。内容大纲基础数据结构树、链表、栈、队列等、常见算法排序算法、递归算法等。
专栏是基于python的基础知识是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念同时结合力扣题目也能更好的掌握这些知识达到在面试中游刃有余的效果。
python基础语法
python基础精讲 http://t.csdnimg.cn/HdKdi
本专栏主要针对python基础语法帮助学习者快速接触并掌握python大部分最重要的语法特征。 1、基本数据类型和变量 2、分支结构与循环结构 3、函数与异常处理 4、类与模块 5、文件读写 通过本专栏可以快速掌握python的基础语法。
