什么是分而治之和动态规划?

这篇具有很好参考价值的文章主要介绍了什么是分而治之和动态规划?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、分而治之

分而治之是算法设计中的一种方法,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并

关于分而治之的实现,都会经历三个步骤:

  • 分解:将原问题分解为若干个规模较小,相对独立,与原问题形式相同的子问题
  • 解决:若子问题规模较小且易于解决时,则直接解。否则,递归地解决各子问题
  • 合并:将各子问题的解合并为原问题的解

实际上,关于分而治之的思想,我们在前面已经使用,例如归并排序的实现,同样经历了实现分而治之的三个步骤:

  • 分解:把数组从中间一分为二

  • 解决:递归地对两个子数组进行归并排序

  • 合并:将两个字数组合并称有序数组

同样关于快速排序的实现,亦如此:

  • 分:选基准,按基准把数组分成两个字数组
  • 解:递归地对两个字数组进行快速排序
  • 合:对两个字数组进行合并

同样二分搜索也能使用分而治之的思想去实现,代码如下:

function binarySearch(arr,l,r,target){
    if(l> r){
        return -1;
    }
    let mid = l + Math.floor((r-l)/2)
    if(arr[mid] === target){
        return mid;
    }else if(arr[mid] < target ){
        return binarySearch(arr,mid + 1,r,target)
    }else{
        return binarySearch(arr,l,mid - 1,target)
    }
}

二、动态规划

动态规划,同样是算法设计中的一种方法,是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

常常适用于有重叠子问题和最优子结构性质的问题

简单来说,动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决

然后呢,把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。

一般这些子问题很相似,可以通过函数关系式递推出来,例如斐波那契数列,我们可以得到公式:当 n 大于 2的时候,F(n) = F(n-1) + F(n-2) ,

f(10)= f(9)+f(8),f(9) = f(8) + f(7)…是重叠子问题,当n = 1、2的时候,对应的值为2,这时候就通过可以使用一个数组记录每一步计算的结果,以此类推,减少不必要的重复计算

适用场景

如果一个问题,可以把所有可能的答案穷举出来,并且穷举出来后,发现存在重叠子问题,就可以考虑使用动态规划

比如一些求最值的场景,如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等,都是动态规划的经典应用场景

关于动态规划题目解决的步骤,一般如下:

  • 描述最优解的结构
  • 递归定义最优解的值
  • 按自底向上的方式计算最优解的值
  • 由计算出的结果构造一个最优解

三、区别

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解

与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的,而分而治之的子问题是相互独立的

若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次

如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间

综上,可得:

  • 动态规划:有最优子结构和重叠子问题

  • 分而治之:各子问题独立

参考文献

  • https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408
  • https://juejin.cn/post/6951922898638471181

更多前端资源请关注 GitHub文章来源地址https://www.toymoban.com/news/detail-811767.html

到了这里,关于什么是分而治之和动态规划?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 动态规划:什么是动态规划?

    动态规划(Dynamic Programming,简称Dp) 是 一种算法思想 : 将原(大)问题化解成子问题,再根据子问题的解得出原问题的解; 状态转移方程 :是一种组合关系,描述了一种原问题与子问题的组合关系 PS: 看着描述和最优子结构问题的描述一样,其实就是一样,一个是文字描述,

    2024年02月08日
    浏览(50)
  • 【面试经典150 | 动态规划】零钱兑换

    【动态规划】【数组】 322. 零钱兑换 定义状态 dp[i] 表示凑成总金额的最少硬币个数。 状态转移 从小到大枚举要凑成的金额 i ,如果当前的金额可以使用面额数组中的某个面额 coin 凑成总金额的一部分,则可以更新 d p [ i ] = m i n ( d p [ i ] , d p [ i − c o i n ] + 1 ) dp[i] = min(dp[i

    2024年04月16日
    浏览(72)
  • 【leetcode刷题之路】面试经典150题(8)——位运算+数学+一维动态规划+多维动态规划

    20 位运算 20.1 【位运算】二进制求和 题目地址:https://leetcode.cn/problems/add-binary/description/?envType=study-plan-v2envId=top-interview-150   按位逆序运算。 20.2 【位运算】颠倒二进制位 题目地址:https://leetcode.cn/problems/reverse-bits/description/?envType=study-plan-v2envId=top-interview-150   详见代码

    2024年04月16日
    浏览(75)
  • 【面试经典150 | 动态规划】交错字符串

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年04月15日
    浏览(69)
  • C/C++ 动态规划面试算法题

    https://blog.csdn.net/qq_41277628/article/details/113322136 输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。 给定

    2024年02月07日
    浏览(38)
  • LeetCode 面试打卡 4: 动态规划 - DataWhale 导学

    动态规划代码实现需要注意的问题 数组 dp 的初始化大小不正确 ,需要根据题目中所给的数据确定好dp数组的大小。一般为[m,n]即可 数组 dp 的初始化逻辑有误 :根据题目条件,初始化dp数组 状态转移方程不正确 :根据题目中的变量设定状态转移方程。 121. 买卖股票的最佳时

    2024年04月24日
    浏览(38)
  • 【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月06日
    浏览(81)
  • 《程序员面试金典(第6版)》 面试题 08.11. 硬币(动态规划,组合问题,C++)

    硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示例1: 输入: n = 5 输出:2 解释: 有两种方式可以凑成总金额: 5=5 5=1+1+1+1+1 示例2: 输入: n = 10 输出:4 解释: 有四种方式可以凑成总金额: 1

    2023年04月08日
    浏览(55)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp(一)

    📦个人主页:一二三o-0-O的博客 🏆技术方向:C/C++客户端资深工程师(直播+音视频剪辑) 👨‍💻作者简介:数据结构算法与音视频领域创作者 📒 系列专栏:牛客网面试必刷 📣专栏目标:帮助伙伴们通过系统训练,掌握数据结构与算法,收获心仪Offer 📝推荐一个找工作

    2024年02月03日
    浏览(73)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp(四)

    📦个人主页:一二三o-0-O的博客 🏆技术方向:C/C++客户端资深工程师(直播+音视频剪辑) 👨‍💻作者简介:数据结构算法与音视频领域创作者 📒 系列专栏:牛客网面试必刷 📣专栏目标:帮助伙伴们通过系统训练,掌握数据结构与算法,收获心仪Offer 📝推荐一个找工作

    2024年02月02日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包