首页 > 其他分享 >动态规划

动态规划

时间:2024-04-12 16:55:40浏览次数:22  
标签:状态 问题 最优 动态 规划 dp

1、动态规划概述

动态规划是一种解决多阶段决策问题的数学优化方法。它将原问题分解成若干个子问题,
通过解决子问题只需解决一次并将结果保存下来,从而避免了重复计算,提高了算法效率。

通俗来讲,动态规划算法是解决一类具有重叠子问题和最优子结构性质的问题的有效方法。其基本原理是将大问题分解为小问题,通过保存中间结果来避免重复计算,从而提高算法的效率。

动态规划主要包括两个要素:最优子结构和重叠子问题。

2、基本概念

  1. 最优子结构(Optimal Substructure): 问题的最优解可以由其子问题的最优解递归地构建而成。
  2. 重叠子问题(Overlapping Subproblems): 问题可以被分解成若干个相同的子问题,这些子问题会被反复解决。
  3. 状态转移方程(State Transition Equation): 用于描述问题的状态和状态之间的关系,通过状态的转移得到最终问题的解。

3、动态规划算法步骤

1.定义状态:确定问题的状态,将大问题分解为子问题,并确定子问题所对应的状态。
2.建立状态转移方程:根据题目要求或者问题的定义,建立子问题之间的递推关系。
3.初始化:确定初始状态的值。
4.递推求解:根据状态转移方程,自底向上地求解问题,直到得到最终的结果。
5.输出结果:根据最终的状态求解结果。

4、区别

分治和动态规划

共同点:都是将问题分解成子问题,然后合并子问题的解得到原问题。
区别:分治分出来的子问题是不重叠的,如归并排序和快速排序(分别处理左右排序,然后将左右序列结果合并),分治解决的问题不一定是最优化问题。
动态规划解决的问题拥有重叠子问题,且一定是最优化问题。

贪心和动态规划

共同点:都要求问题拥有最优子结构。
贪心:整个过程以单链的流水方式进行,显然这种“最优的选择”的正确性需要用归纳法证明。例如数塔问题,贪心从最上层开始,每次选择左下或右下较大的那个,一直到最底层得到结果,显然这不一定可以得到最优解。
动态规划:无论采用自底向上还是自顶向下的方法,都是从边界向上得到最优解,它总是会考虑所有子问题,并选择继承能得到最优结果那个,对于暂时没被继承的子问题,由于重叠子问题的存在,后期可能会再次考虑它,
因此还有机会成为全局最优的一部分,不需要放弃。

5、应用

动态规划广泛应用于解决一些优化问题,如最短路径问题、最长公共子序列、背包问题等。以下是一些常见的应用场景:

最短路径问题: 比如 Dijkstra 算法和 Floyd-Warshall 算法。

背包问题: 包括 0/1 背包问题和背包问题的变种。

最长公共子序列: 求解两个序列的最长公共子序列的长度。

字符串编辑距离: 计算两个字符串之间的最小编辑操作次数,包括插入、删除和替换。

最大子数组和: 求解数组中连续子数组的最大和。

示例:假设有一个数组 nums,求解其连续子数组的最大和

动态规划解法:

定义状态: 设 dp[i] 为以 nums[i] 结尾的连续子数组的最大和。

状态转移方程: dp[i] = max(dp[i-1] + nums[i], nums[i]),即当前位置的最大和要么是之前的最大和加上当前元素,要么是当前元素本身。

初始化: dp[0] = nums[0],数组的第一个元素作为初始值。

遍历: 从数组的第二个元素开始遍历,更新 dp[i]。

最终结果: 最大的 dp[i] 即为所求。

 

标签:状态,问题,最优,动态,规划,dp
From: https://www.cnblogs.com/Zhouce/p/18131653

相关文章

  • MyBatis动态SQL
    MyBatis动态SQL动态SQL简介动态SQL是MyBatis的强大特性之一。如果你使用过JDBC或其它类似的框架,你应该能理解根据不同条件拼接SQL语句有多痛苦,例如拼接时要确保不能忘记添加必要的空格,还要注意去掉列表最后一个列名的逗号。利用动态SQL,可以彻底摆脱这种痛苦。使用动态......
  • C++——线性动态规划
    线性动态规划引入:1.爬楼梯爬楼梯类型的问题可谓是线性DP的入门题目以及经典中的经典。我们先来看一下题目。爬楼梯题目描述有一天,三萩实在太无聊了,竟然无聊到去数台阶了。有一个楼梯一共有m级,刚开始三萩在第一级,他就想,若每次只能跨上一级或者二级,要走上m级,共有多少种走法?......
  • el-table实现动态数据的实时排序,一篇文章讲清楚elementui的表格排序功能,利用@sort-cha
        写这篇博客的原因是前段时间做了一个数据列可变的表格,同时需要实现在网页中更新了数据列之后,能够对表格进行排序的需求。如果想要直接了解实现el-table的动态数据动态排序(列数据是通过计算获得,并且可以在页面中修改,在此基础上实现数据变化后实时更新)。请直接跳到......
  • 多级动态表头导出-easyexcel
    导出如下动态表头 主要的构造tabCols和tableData,注意表头的字段,基本构造出了该格式所有的都能适配@GetMapping("/exportData")publicvoidexcelExport(TbDtTargetHealthMontbDtTargetHealthMon,HttpServletResponseresponse)throwsIOException{re......
  • Day37代码随想录(1刷) 动态规划
    509.斐波那契数斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:F(0)=0,F(1) =1F(n)=F(n-1)+F(n-2),其中n>1给定 n ,请计算 F(n) 。示例1:输入:n=2输出:1解......
  • 动态规划dp
    动态规划(Dp)介绍动态规划(Dynamicprogramming)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划问题的特点1.最优子结构性质:如果问题的最优......
  • Ubuntu-kali配置动态ip(简单)
    使用gedit文本编辑器打开网络接口配置文件gedit/etc/network/interfaces新增两行内容如下:autoeth0ifaceeth0inetdhcp其意思为:网卡开机自动挂载,以DHCP方式配置网卡。点击保存后叉掉。同样,使用文本编辑器打开resolv.conf配置文件。该配置文件主要作用是解析域名ged......
  • 动态规划Dp
    什么是动态规划?动态规划(英语:Dynamicprogramming,简称DP),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。以上定义来自维基百科,看定义......
  • 【多UAV航迹规划】基于ACO蚁群优化的多UAV航迹规划算法matlab仿真
    目录1.算法仿真效果2.MATLAB源码3.算法概述3.1ACO蚁群优化算法原理......
  • ROS中自定义全局算法规划器(c++)
     ros中编写一个全局路径规划器并集成为ros插件,加载到turtlebot3机器人平台上仿真验证参考资料:ROS中自定义全局规划器(上)_算法部署_哔哩哔哩_bilibili官网教程:navigation/Tutorials/WritingAGlobalPathPlannerAsPlugininROS-ROSWiki1.建立工作空间mkdir-pjps_......