动态规划与贪心算法:核心区别与实例分析

动态规划与贪心算法:核心区别与实例分析

动态规划和贪心算法是计算机科学中用于解决优化问题的两种著名方法。它们各自的思路和应用场景有显著的区别,理解这些区别对解决相关问题至关重要。本文将详细探讨这两种算法的最优子结构、解法策略、适用场景,并通过具体的代码示例加以说明。

一、最优子结构

动态规划(Dynamic Programming, DP)

动态规划适用于具有最优子结构性质的问题。也就是说,问题的最优解可由其子问题的最优解组合而成。在 DP 中,通常会存储和复用这些子问题的结果,以避免重复计算,从而提高效率。

例子:斐波那契数列

动态规划可以用来高效地计算斐波那契数列。

public class Fibonacci {public int fib(int n) {if (n <= 1) return n;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移}return dp[n];}
}

贪心算法(Greedy Algorithm)

贪心算法适用于通过局部最优选择来构造全局最优解的问题。在每一步,贪心算法都选择当前最优选项,而不考虑全局最优解,这种方法虽不保证最佳解,但在特定问题下可以得到全局最优解。

例子:找零问题

在给定硬币面额的情况下,贪心算法可以用来找零。

public class CoinChange {public int minCoins(int[] coins, int amount) {Arrays.sort(coins); // 先排序,贪心选择最大面额的硬币int count = 0;for (int i = coins.length - 1; i >= 0; i--) {while (amount >= coins[i]) {amount -= coins[i];count++;}}return count; // 最少硬币数量}
}

二、解法策略

动态规划的策略

  1. 自底向上:通过先解决较小的子问题,逐步构建出最终解决方案。
  2. 状态转移:定义状态的转换规则,从而构造 DP 表。

贪心算法的策略

  1. 自顶向下:逐步构造解决方案,每一步都选择当前认为最佳的选项。
  2. 局部最优选择:在当前状态下选择最优选项,构建全局解决方案。

三、适用场景

1. 动态规划的适用场景

动态规划通常适用于需要考虑所有可能选项的场景,典型问题包括:

  • 背包问题
  • 最长公共子序列
  • 最短路径问题(如 Dijkstra 算法)
  • 编辑距离
例子:最长公共子序列
public class LongestCommonSubsequence {public int lcs(String text1, String text2) {int[][] dp = new int[text1.length() + 1][text2.length() + 1];for (int i = 1; i <= text1.length(); i++) {for (int j = 1; j <= text2.length(); j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[text1.length()][text2.length()];}
}

2. 贪心算法的适用场景

贪心算法则适用于那些局部选择能够构建全局解决方案的情况,例如:

  • 活动选择问题
  • 霍夫曼编码
  • 最小生成树(Prim/Kruskal 算法)
例子:最小生成树(Kruskal 算法)
public class KruskalAlgorithm {public List<Edge> kruskal(List<Edge> edges, int numVertices) {Collections.sort(edges); // 按权重排序UnionFind uf = new UnionFind(numVertices);List<Edge> result = new ArrayList<>();for (Edge edge : edges) {if (uf.find(edge.src) != uf.find(edge.dest)) {uf.union(edge.src, edge.dest);result.add(edge); // 选择此边}}return result; // 返回最小生成树的边}
}

四、总结

  • 动态规划:通过记忆化存储中间状态以减少计算量,适合状态具有重叠子问题的情况。它是解决复杂问题的强大工具。

  • 贪心算法:通过在每一步选择中做出局部最优解,适合解决能够通过局部选择构建全局解决方案的问题。

在实际的应用中,选择使用动态规划还是贪心算法,取决于问题的性质及其最优解的结构。理解这两者的区别与联系是解决许多优化问题的关键所在。

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

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

相关文章

快速学习Serde包实现rust对象序列化

在处理HTTP请求时&#xff0c;我们总是需要在数据结构对象&#xff08;可以是enum、struct等&#xff09;和序列化数据格式&#xff08;例如JSON&#xff0c;用与存储或传输&#xff0c;并可以反序列化的格式&#xff09;之间来回转换。 Serde是一个库&#xff08;crate&#x…

OLED 显示画面的变换操作——上下、左右翻转

OLED 画面旋转 OLED 写入函数定义 OLED_WR_Byte(0xA1,OLED_CMD);//--Set SEG/Column Mapping 0xa0左右反置 0xa1正常 OLED_WR_Byte(0xC8,OLED_CMD);//Set COM/Row Scan Direction 0xc0上下反置 0xc8正常OLED 显示界面转换函数如下 void OLED_DisplayTurn(u8 i) {if(i0…

由播客转向个人定制的音频频道(1)平台搭建

项目的背景 最近开始听喜马拉雅播客的内容&#xff0c;但是发现许多不方便的地方。 休息的时候收听喜马拉雅&#xff0c;但是还需要不断地选择喜马拉雅的内容&#xff0c;比较麻烦&#xff0c;而且黑灯操作反而伤眼睛。 喜马拉雅为代表的播客平台都是VOD 形式的&#xff0…

luckfox-pico-max学习记录

0.文件编译及烧录 SDK包在文件夹/home/tao/linux/luckfox/luckfox-pico-spi应用程序样例在文件夹/home/tao/linux/luckfox-pico-spi/demo编译&#xff1a;sudo ./build.sh生成的镜像文件在./luckfox-pico-spi/output/image中&#xff0c;将所有文件复制到windows电脑文件夹I:\…

一文了解珈和科技在农业遥感领域的服务内容和能力

2020年&#xff0c;农业农村部、中央网信办联合印发了《数字农业农村发展规划&#xff08;2019-2025年&#xff09;》&#xff0c;对数字农业农村建设作出了具体部署。其中&#xff0c;农业遥感作为推进数字农业农村的重要力量贯穿《规划》始终。 今年10月&#xff0c;农业农村…

羊城杯2020Easyphp

审题 看到url&#xff0c;可以想到伪协议读取 尝试过后可以发现&#xff0c;题目绕过了read后面的编码 我们可以尝试双重urlencode进行绕过 ?filephp://filter/read%25%36%33%25%36%66%25%36%65%25%37%36%25%36%35%25%37%32%25%37%34%25%32%65%25%36%32%25%36%31%25%37%33%…

【时间之外】IT人求职和创业应知【34】-人和机器人,机器人更可靠

目录 新闻一&#xff1a;人形机器人产业持续高速增长&#xff0c;2026年中国市场规模将突破200亿元 新闻二&#xff1a;AI技术驱动设备厂商格局变化&#xff0c;部分厂商市占率快速提升 新闻三&#xff1a;华为与江淮汽车携手打造超高端品牌“尊界”&#xff0c;计划于明年春…

Linux——基础指令2 + 权限

目录 1.zip/unzip 2.tar 3.bc 4.uname –r 5.重要的几个热键 6.扩展命令 7.shell命令以及运行原理 8.Linux权限的理解 关于权限的三个问题&#xff1a; 1.目录权限 2.缺省权限 3.粘滞位 1.zip/unzip 打包、压缩&#xff1a;使用特定的算法&#xff0c;文件进行合…

pgsql和mysql的自增主键差异

1. 当有历史数据存在时&#xff0c; mysql的自增主键是默认从最大值自增。 pgsql的自增主键取初始值开始逐个尝试&#xff0c;所以存在可能与历史数据的主键重复的情况。 pgsql解决上述问题的方式&#xff1a;重设自增值。 SELECT SETVAL(t_db_filed_id_seq, (SELECT MAX(&q…

【Linux】基础IO及文件描述符相关内容详细梳理

0. C语言文件I/O 在C语言中&#xff0c;我们学习了相关函数来读写文件&#xff0c;例如&#xff1a;fopen&#xff0c;fwrite&#xff0c;fread&#xff0c;fprintf等&#xff0c; 在C语言中文件的打开方式&#xff1a; r Open text file for reading. …

大语言模型在序列推荐中的应用

一、简介 序列推荐技术通过分析用户的过往交互历史&#xff0c;能够有效挖掘出用户可能感兴趣的项目&#xff0c;对于提升各类应用的服务质量具有重要作用。近期&#xff0c;大语言模型&#xff08;LLMs&#xff09;的发展在应对复杂的推荐问题上展现出了显著的优势。不过&…

JavaScript——函数、事件与BOM对象

一、系统函数(JS中预置的函数) JS的预置函数在遇到非数字字符时会停止解析 parseInt 转整型 parseFloat 转浮点型 isNaN !isNaN("10") 检测是否纯数字 eval 把字符串转成算式并计算 1.parseInt(string, radix); 语法&#xff1a; string&#x…

Python酷库之旅-第三方库Pandas(208)

目录 一、用法精讲 971、pandas.MultiIndex.set_levels方法 971-1、语法 971-2、参数 971-3、功能 971-4、返回值 971-5、说明 971-6、用法 971-6-1、数据准备 971-6-2、代码示例 971-6-3、结果输出 972、pandas.MultiIndex.from_arrays类方法 972-1、语法 972-2…

相亲小程序(源码+文档+部署+讲解)

最近我在挖掘一些优秀的开源项目时&#xff0c;无意间发现了一个相当给力的系统——相亲小程序管理系统。这个系统不仅功能实用&#xff0c;而且代码结构清晰&#xff0c;易于二次开发。作为一名技术爱好者&#xff0c;我觉得有必要把这个好东西推荐给我的读者们。接下来&#…

spring cloud 入门笔记1(RestTemplate,Consul)

最大感受&#xff1a; spring cloud无非是将spring boot中的各个工作模块拆分成独立的小spring boot&#xff0c;各个模块之间&#xff0c;不再是通过导包什么的&#xff0c;调用而是通过网路进行各个模块之间的调用 工具一&#xff1a;RestTemplate 在Java代码中发送HTTP请…

高性能分布式缓存Redis-高可用部署

一、主从架构搭建 为什么要进行主从架构搭建&#xff0c;一台redis不行吗&#xff1f; ①、持久化后的数据只在一台机器上&#xff0c;因此当硬件发生故障时&#xff0c;比如主板或CPU坏了&#xff0c;这时候无法重启服务器&#xff0c;有什么办法可以保证服务器发生故障时数…

新的恶意软件活动通过游戏应用程序瞄准 Windows 用户

一种新的恶意软件 Winos4.0 被积极用于网络攻击活动。FortiGuard实验室发现&#xff0c;这种先进的恶意框架是从臭名昭著的 Gh0strat 演变而来的&#xff0c;配备了模块化组件&#xff0c;可在受感染的设备上进行一系列恶意活动。 这些攻击已在游戏相关应用程序中发现&#xf…

Python教程笔记(1)

Python教程笔记 3.1.1 数字3.1.2 文本3.1.3 列表4.2 for语句4.3 range()函数4.7 match语句4.8 定义函数4.9.1 默认值参数4.9.3 特殊参数4.9.5. 解包实参列表 对官方教程中自我感觉生疏的知识点做个记录&#xff0c;以便后面回顾。 3.1.1 数字 除法运算 (/) 总是返回浮点数。 如…

C++笔记---异常

1. 异常的概念 1.1 异常和错误 异常通常是指在程序运行中动态出现的非正常情况&#xff0c;这些情况往往是可以预见并可以在不停止程序的情况下动态地进行处理的。 错误通常是指那些会导致程序终止的&#xff0c;无法动态处理的非正常情况。例如&#xff0c;越界访问、栈溢出…

【RabbitMQ】08-延迟消息

1. 延迟消息 2. 死信交换机 正常队列不需要接受消息。 Configuration public class NormalQueueConfig {Beanpublic DirectExchange normalExchange() {return new DirectExchange("normal.direct");}Beanpublic Queue normalQueue() {return QueueBuilder.durable(…