手机网站404页面,windows优化大师怎么样,做招聘网站需要多少钱,遵义网站建设哪家好?动态规划#xff1a;
dynamic programming。programming指的是一种表格法#xff0c;而非编写计算机程序。通常解决最优化问题#xff08;optimization problem#xff09;。将问题拆分成若干个子问题#xff0c;求解各子问题来得到原问题的解。适用于多阶段…动态规划
dynamic programming。programming指的是一种表格法而非编写计算机程序。通常解决最优化问题optimization problem。将问题拆分成若干个子问题求解各子问题来得到原问题的解。适用于多阶段决策以时间划分阶段的动态过程可人为引进时间因素。即一个活动过程可划分多个互相关联的阶段每个阶段都需做决策一个阶段的决策影响下一个阶段的决策从而确定一个活动路线即策略每个阶段的决策组成的序列。使用条件最优子结构一个问题最优解包含其子问题的最优解重叠子问题问题的递归算法会反复求解相同的子问题而不是一直生成新的子问题。每个子问题只计算一次即有一个表记录每个子问题的解再次需要该子问题时直接查表无需重复计算。两种方法带备忘的自顶向下递归。从整体开始拆分多个子问题递归求解自底向上迭代。先解决最小问题进而解决整体问题。通常使用自底向上。关键解决冗余以空间换时间占用额外的内存但节省计算时间。缺点“维数障碍”维度增加空间复杂程度呈指数级增长没有统一的处理方法具体问题具体分析。 动态规划、分治方法、贪心算法都是将问题分成若干个子问题求解子问题从而得到原问题的解。 动态规划与分治方法的区别
动态规划的子问题相互重叠、不是独立的。分治方法的子问题互不相交、相互独立。动态规划的子问题只计算一次并保存子问题的解。分治方法会计算每次出现的子问题。若同样的问题使用分治方法则会重复计算相同的子问题。
动态规划与贪心算法的区别
动态规划寻求全局最优解相关的子问题全部解决了才能做出选择。贪心算法是贪心地追求局部最优解即当前状态下最优选择求解选出的子问题的解不一定全局最优解。 案例
1、难度简单【力扣】746. 使用最小花费爬楼梯 解题思路台阶0和台阶1均可为起始点即花费为0此后到达各台阶含目的地的最小花费min前1个台阶走1步到达的最小花费前2个台阶走2步到达的最小花费。有一个列表记录到达各台阶含目的地的最小累积花费。
知识点min(a, b)从a和b中获取最小值。
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost) # 数组长度res [0] * (n 1) # 记录到达各台阶和目的地的累积花费 # 从下标为0或1开始花费为0忽略# 从下标为2开始判断前1个台阶到这和前2个台阶到这的累积最小花费添加到结果列表中for i in range(2, n 1):res[i] min(res[i - 1] cost[i - 1], res[i - 2] cost[i - 2])# 返回到达目的地时的累积花费return res[n] 优化各台阶含目的地花费涉及前1个台阶走1步的花费前2个台阶走2步的花费其中最小的值。
设置3个变量prev当前台阶的前1个台阶走2步到下一个需到达的台阶curr当前台阶走1步到下一个需到达的台阶next下一个需到达的台阶。
返回最终到达当前台阶的累积最小花费。
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost) # 数组长度prev, curr 0, 0 # prev前1个台阶curr当前台阶# 从下标为0或1开始花费为0忽略# 从下标为2开始计算到达该台阶的累积花费# 当前台阶走1步到下一个台阶和前1个台阶走2步到下一个台阶的累积最小花费for i in range(2, n 1):next min(curr cost[i - 1], prev cost[i - 2])prev, curr curr, next # 向后滚动移动return curr python中itertools模块中pairwise可依次生成连续的两个元素。
itertools.pairwise(可迭代对象返回迭代器迭代器中为依次生成的连续的2个元素。 class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost) # 数组长度prev, curr 0, 0 # prev前1个台阶curr当前台阶# 从下标为0或1开始花费为0忽略# 从下标为2开始计算到达该台阶的累积花费# 当前台阶走1步到下一个台阶和前1个台阶走2步到下一个台阶的累积最小花费import itertoolsfor a, b in itertools.pairwise(cost):next min(prev a, curr b)prev, curr curr, next # 向后滚动移动return curr 2、难度中等【力扣】714. 买卖股票的最佳时机含手续费 解题思路有一个二维数组记录每一日最大收益max若当日手上没有股票时的最大收益若当日手上有股票时的最大收益。
知识点[ [ 0,0] ] * n二维数组有n个元素元素类型仍为数组。即[[0,0],[0,0],...,[0,0]]。 二维数组[0][1]获取二维数组的第一个元素中下标为1的值。 max(a, b)从a和b中获取最大值。
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:n len(prices)# 二维数组初始化记录[第i日手上没股票的收益,第i日手上有股票的收益]res [[0, 0]] * n# 第1日res列表中下标为0的元组,下标为0的值为0第1日手上没有股票的收益忽略# 第1日res列表中下标为0的元组,下标为1的值为付出的买入价第1日手上有股票的收益res[0][1] -prices[0] # 遍历每日价格for i in range(1, n):# 当日,手上没有股票的收益:前1日也没股票前1日有股票今天卖掉取最大值res[i][0] max(res[i - 1][0], res[i - 1][1] prices[i] - fee)# 当日,手上有股票的收益前1日也有股票前1日没股票今天买入取最大值res[i][1] max(res[i - 1][1], res[i - 1][0] - prices[i])# 最后手上没有股票收益更大return res[n - 1][0] 优化今日收益涉及前1日手上是否有股票。滚动记录。
设置2个变量zero当日若手上没有股票时的收益。one当日若手上有股票时的收益。
返回最终手上没有股票时的收益。
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:n len(prices)# 第1日zero:手上没有股票的收益one:手上有股票的收益(付出的买入价)zero, one 0, -prices[0]# 遍历每日价格for i in (range(1, n)):# 当日手上没有股票的收益前1日也没股票前1日有股票今天卖掉取最大值zero max(zero, one prices[i] - fee)# 当日手上有股票的收益前1日也有股票前1日没有股票今天买入取最大值one max(one, zero - prices[i])# 最后手上没有股票收益最大return zero 注本题其他解题方法贪心算法 3、难度困难【力扣】871. 最低加油次数 解题思路遍历每个加油站先假设每到一个加油站都加油i个加油站最多加油 i 次。
要求加油次数尽可能少为避免重复加油依次减少到达该加油站的加油次数j从i到0滚动调整加油 j 次后可行驶最大距离max已加油 j次 在本加油站不加油的最大距离已加油 j-1次 在本加油站加油后最大距离。
最后遍历加油 j次后可行驶的最大距离大于等于目的地的距离则返回下标即加了几次油否则无法到达目的地返回-1。
知识点enumerate(可迭代对象)返回所有的元素下标和元素内容元组形式。一般用于for循环。
class Solution:def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) - int: res [0] * (len(stations) 1) # 记录每次加油后含初始油量可以行使的最大距离 res[0] startFuel # 初始油量可以行使的最大距离# 遍历每个加油站for i, (long, fuel) in enumerate(stations):# 先假设每到一个加油站就加油,再减少到这的加油次数,滚动调整加油j次(i到0)后可行使的最大距离# 例如到达第3个加油站后最多加油3次# 若加油3次最大行驶距离max(已加油3次本次不加油最大距离, 已加油2次本次再加油后最大距离)# 若加油2次最大行驶距离max(已加油2次本次不加油最大距离, 已加油1次本次再加油后最大距离)# 若加油1次最大行驶距离max(已加油1次本次不加油最大距离, 已加油0次本次再加油后最大距离) for j in range(i, -1, -1): # 倒序避免重复加油# 到达加油站后才判断在这是否加油以及加油j次后可行驶最大距离if res[j] long:res[j 1] max(res[j 1], res[j] fuel)# 遍历加油j次后的最大行使距离超过目的地则返回下标即加了几次油for j, val in enumerate(res):if val target: return jreturn -1
注本题其他解题方法贪心算法
