动态规划:入门思考篇

1. 简单类比

假如我们要求全国人数,那么我们只要知道各个省的人数,然后将各个省的人数相加即可,要想知道各个省的人数,只要将这个省下面所有的市人数相加即可,同样,如果想要知道各个市的人数,只要知道下面所有县的人数即可。

这就是动态规划的核心思想:将原问题拆解为更小的子问题,求解每个子问题的最优解后,通过组合子问题的解得到原问题的解

类比逻辑动态规划核心概念关键说明
全国人数(最终目标)原问题(Original Problem)需要求解的最终复杂问题。
省 / 市 / 县人数子问题(Subproblems)原问题拆解出的、规模更小的同类问题(子问题需与原问题 “同结构”,如都是 “统计某区域人数”)。
省 = 市相加 / 市 = 县相加状态转移方程(State Transition)子问题的解如何组合成父问题的解(你的例子中是 “求和”,DP 中可能是 “取最大 / 最小 / 累加” 等)。
县人数(最底层)边界条件(Base Case)无需再拆解的最小子问题,有直接已知的解(如 “某县人数 = 统计局直接公布的数据”,无需再拆到乡镇)。

在这里插入图片描述

2. “分治” 与 “最优子结构”

如果我们有很多种解决方案,但是我们想要找出最优的方案。一种方法就是,我们将所有的方案划分成不同的集合,这些集合之间互不重叠,结合内部也没有重合的方案,此时我们只要求解出各个集合的最优方案,然后从最优方案中选出最优即可。

要确保通过 “划分集合→找集合最优→选最终最优” 能得到全局最优解,需满足以下两点,这是避免 “漏掉最优方案” 或 “选不出真最优” 的核心:

  • 前提 1:集合的 “完全覆盖性”
    划分的所有集合必须覆盖全部可能的解决方案,不能有遗漏。
    例如:若要选 “从家到公司的最优路线”,若只划分 “走地铁” 和 “骑自行车” 的集合,却漏掉 “坐公交” 的集合,可能恰好 “坐公交” 是耗时最短的最优方案,最终结果就会出错。
  • 前提 2:“最优子结构” 成立
    每个集合的 “局部最优方案”,必须是支撑 “全局最优方案” 的候选。换句话说,全局最优方案一定来自某个集合的局部最优方案,不会存在 “某个集合的非最优方案,比所有集合的最优方案更好” 的情况。
    例如:若划分 “从家到公司走东边” 和 “走西边” 两个集合,若 “东边集合的最优路线(20 分钟)” 和 “西边集合的最优路线(25 分钟)”,则全局最优一定是东边的 20 分钟,不会存在 “东边集合里某条 22 分钟的路线,比西边最优还快” 的矛盾 —— 这就是最优子结构的体现。
你的通用框架动态规划(DP)的补充细节贪心算法的补充细节
划分互不重叠的方案集合划分的 “集合” 对应 “子问题”,且子问题存在重叠性(需存储解避免重复计算)划分的 “集合” 对应 “每一步的选择”,且需满足贪心选择性质(每步选局部最优就能推全局最优)
求每个集合的最优方案通过 “状态转移方程” 计算子问题最优解(依赖更小的子问题)直接选择当前集合的 “局部最优”(无需依赖后续子问题,一步到位)
从局部最优中选全局最优最终问题的解就是最顶层子问题的最优解所有步骤的局部最优累加 / 组合,直接得到全局最优

3. 青蛙跳台阶

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

我们想要知道n阶的方案数,只要知道n-1阶的方案数和n-2阶的方案数即可。假如n=5

  1. 跳到第4阶的方案集合
    1->2->3->4->5
    1->2->4->5
    2->4->5
    2->3->4->5
    
  2. 跳到第3阶的方案集合
    1->2->3->5
    2->3->5
    1->3->5
    

总之要想跳到第5阶,那么一定是从第3阶或者第4阶过来的,方案数也就是这两种集合方案数的和。我不知道跳到第4的阶的方案是什么,也不知道跳到第3阶的方案是什么,但是按照第3阶和第4阶,我可以将跳到第5阶所有的方案分成不重合的两个集合,只要求出这两个集合的方案数,然后相加就是最后的方案数。

这两个集合把所有的方案不重不漏的划分开来,符合无重叠性和完全覆盖性。第一个集合的所有方案,最后一步必然经过第4阶台阶,第二个集合的所有方案,最后一步必然经过第3阶台阶。

4. 集合的唯一划分标准

这里有一个困惑,集合一中不是也会有方案经过3吗,为什么不会与集合二重叠呢?

两个集合的划分标准是 “最后一步的来源”,而非 “方案是否经过某个中间台阶”,因此即使集合一的方案经过 3 阶,也不会与集合二重叠

  • 集合一(来自 n-1 阶):所有方案的最后一步是 “从第 4 阶跳 1 阶到第 5 阶”(无论这个方案在到达 4 阶之前,是否经过 3 阶、2 阶等)。
    例:方案 “1→2→3→4→5”,最后一步是 “4→5”,属于集合一;哪怕方案是 “1→3→4→5”,最后一步仍是 “4→5”,也属于集合一。
  • 集合二(来自 n-2 阶):所有方案的最后一步是 “从第 3 阶跳 2 阶到第 5 阶”(无论这个方案在到达 3 阶之前,是否经过 2 阶、1 阶等)。
    例:方案 “1→2→3→5”,最后一步是 “3→5”,属于集合二;哪怕方案是 “1→3→5”,最后一步仍是 “3→5”,也属于集合二。

一个方案的 “最后一步” 是唯一的、不可拆分的,这是避免重叠的核心:

  • 集合一的方案,无论中间是否经过 3 阶,其 “最后一步” 必然是 “4→5”(跳 1 阶);
  • 集合二的方案,无论中间是否经过其他台阶,其 “最后一步” 必然是 “3→5”(跳 2 阶)。

这就像 “无论你之前走了哪条路,最后一步是‘迈左脚进门’还是‘迈右脚进门’,是完全不同的两个动作”—— 不会存在一个方案,“最后一步既从 4 阶跳 1 阶,又从 3 阶跳 2 阶”,因此两个集合绝对无重叠。

5. 01背包问题

有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
比如有3个物品,a,b,c,d每个物品的价值为10, 15,20,30,重量分别为1,2,2,3,背包的重量为4

我们有2N2^N2N中选择,也就有2N2^N2N中方案,我们从这些方案中选择一个最优的方案,能装下的价值最大。

如果我们能将所有的方案分组,然后获取每个组内的最大价值,那么最大的那个价值就是最终的价值。一种简单的划分就是我们是否选择某个物品,例如我们是否选择a

  1. 选择a的方案
    a
    a, b
    a, c
    a, d
    a, b, c
    a, b, d
    a, c ,d
    
  2. 不选择a的方案
    b
    b, c
    b, d
    c
    c,d
    d
    

可以看到两种方案完全没有重合,因为集合一全部的方案都包含a,集合二所有的方案都不包含a,通过这种集合划分方式,我们得到了所有的方案,并且两个集合中没有重复的方案。对于集合一和集合二,我们可以再次通过是否选择b划分为更小的集合。
在这里插入图片描述

子问题重叠

你的类比中,子问题(省、市、县)是 “互不重叠” 的(一个县只属于一个市,一个市只属于一个省),而动态规划的典型场景中,子问题往往是 “重叠” 的(即不同父问题可能依赖同一个子问题的解)。

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

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

相关文章

小杨的 X 字矩阵(举一反三)-洛谷B3865 [GESP202309 二级]

题目描述 小杨想要构造一个 X 字矩阵( 为奇数),这个矩阵的两条对角线都是半角加号 ,其余都是半角减号 - 。例如,一个 55 的 X 字矩阵如下: --- --- ---- --- --- 请你帮小杨根据给定的 打印出对应的“X …

数据组合与合并:Pandas 数据整合全指南 +缺失值处理

数据组合与合并:Pandas 数据整合全指南在进行数据分析之前,数据清洗与整合是关键步骤。 遵循“整洁数据”(Tidy Data)原则: 每个观测值占一行每个变量占一列每种观测单元构成一张独立的表格 整理好数据后,常…

c#联合halcon的基础教程(案例:亮度计算、角度计算和缺陷检测)(含halcon代码)

目录 1.环境配置 2.案例一:亮度计算 halcon代码: 主界面代码: 3.案例二: 角度计算 halcon代码: 主界面代码: 4.案例三:缺陷检测 halcon代码: 主界面代码: 通过…

大数据云原生是什么

"云原生"(Cloud Native)指的是‌利用云计算原生优势(弹性、按需服务、自动化、分布式等)来设计、构建、部署和运行大数据应用和工作负载的方法论与技术体系‌。它不是简单地“把大数据平台搬到云上”,而是从…

Pytest项目_day16(yaml和parametrize结合)

查询手机号归属地 我们首先可以在YAML文件中定义测试数据 方式一,使用- 注意:当我们需要一次传入两个参数时,需要定义两层迭代,即两层列表不够直观,容易写错 输出的结果为: 然后我们可以将测试数据传入test…

【Nginx指南】从核心原理到生产实践

目录Nginx指南:从核心原理到生产实践引言:Nginx在现代架构中的核心地位一、Nginx核心能力与应用场景1.1 多场景适配的全能型中间件1.2 技术优势:Nginx成为行业标准的关键二、Nginx安装部署:源码编译与包管理方案2.1 源码编译&…

物体检测

目录 1 目标定位 2 地标检测 3 目标检测 4 在卷积网络上实现滑动窗口 5 边界框预测 6 交并比 7 非极大值抑制 8 锚框 9 YOLO算法 10 用u-net进行语义分割 11 转置卷积 12 u-net 结构灵感 1 目标定位 你已经对图片分类有所了解。例如通过这张图片可以识…

es7.x es的高亮与solr高亮查询的对比对比说明

一 solr&es高亮1.1 solr与es高亮功能解释说明:1)高亮配置:fragmentSize(1000) 设置片段长度numOfFragments(1) 指定返回的片段数量preTags() 和 postTags() 设置高亮标记2)字段处理差异:在 ES 中,使用 matchQuery 而非 termQ…

DSP音频算法工程师技能2

一、核心知识准备1. 算法原理3A算法(AGC自动增益控制/AEC回声消除/ANS降噪):掌握AEC的NLMS/双讲检测原理,ANS的谱减法/维纳滤波,AGC的压缩曲线设计。熟悉Speex/WebRTC等开源实现。EQ音效:IIR/FIR滤波器设计…

第4章-04-用WebDriver页面元素操作

🏆作者简介,黑夜开发者,CSDN领军人物,全栈领域优质创作者✌,CSDN博客专家,阿里云社区专家博主,2023年CSDN全站百大博主。 🏆数年电商行业从业经验,历任核心研发工程师,项目技术负责人。 🏆本文已收录于专栏:Web爬虫入门与实战精讲,后续完整更新内容如下。 文章…

【计算机视觉与深度学习实战】04基于K-Means聚类的图像分割系统设计与实现

摘要 图像分割作为计算机视觉领域的基础任务,在目标检测、医学影像分析、自动驾驶等众多应用中发挥着关键作用。本文基于K-Means聚类算法设计并实现了一个完整的图像分割系统,该系统集成了多种颜色空间转换、自定义初始化策略、空间特征融合等先进技术。通过Python和Tkinter…

Android Studio常用知识总结

一、运行方式1.运行 (Run)当您选择“运行”时,Android Studio 会编译您的应用并将其安装到目标设备或模拟器上。这通常用于:快速部署: 您只想看看应用是否能正常启动并运行,或者进行一些基础的用户界面测试。性能测试: 在正常运行模式下测试应…

设计模式笔记_行为型_访问者模式

1. 访问者模式介绍访问者模式(Visitor Pattern)是一种行为型设计模式,它允许你在不改变对象结构的前提下,定义作用于这些对象的新操作。访问者模式将操作的逻辑从对象结构中分离出来,使得你可以在运行时动态地添加新的…

数学建模 14 中心对数比变换

用途:是处理成分数据的核心预处理方法,核心目标是解决成分数据的和为常数100% , 导致的维度冗余,非线性相关问题。使得数据满足传统的统计/建模方法;举例子:食品比例中 面粉(50%),糖(30%),水(20%)原理&…

【C语言强化训练16天】--从基础到进阶的蜕变之旅:Day7

🔥个人主页:草莓熊Lotso 🎬作者简介:C研发方向学习者 📖个人专栏: 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》 ⭐️人生格言:生活是默默的坚持,毅力是永久的…

污水处理行业的 “智能革命”:边缘计算网关如何重塑传统运维模式?

污水处理行业的 “智能革命”:边缘计算网关如何重塑传统运维模式?在污水处理这一关乎生态环境与可持续发展的关键领域,蓝蜂网关正凭借其先进技术与强大功能,发挥着无可替代的重要作用。作为工业级物联网解决方案的核心组件&#x…

ASP.NET Core 中的多租户 SaaS 应用程序

介绍随着软件即服务 (SaaS) 持续主导技术领域,构建能够高效地从单一代码库服务于多位客户(租户)的应用程序变得至关重要。ASP.NET Core 凭借其模块化和可扩展的架构,是实现多租户 SaaS 应用程序的强大框架。本文将指导您了解构建多…

JUC之CompletableFuture【中】

文章目录四、CompletableFuture基本使用4.1 默认线程池、无返回值4.2 默认线程池、有返回值4.3 自定义线程池、有返回值4.4 CompletableFuture 获取结果五、对结果进行处理5.1 方法说明5.2 示例5.3 thenApply vs thenApplyAsync5.3.1 核心区别: 执行线程不同5.3.2 thenApply: 同…

环境变量不生效?

目录 添加环境变量 解决不生效 不生效场景 解决办法 大家都知道Windows系统对于开发者来说并不友好,尤其是新手,当然这是相比于linux和MacOS相比,因为开发工具、项目脚本等环境配置要为复杂,注意事项也更多一些。而这篇文章将…

小迪安全v2023学习笔记(六十六讲)—— Java安全SQL注入SSTISPELXXE

文章目录前记WEB攻防——第六十六天Java安全&SPEL表达式&SSTI模板注入&XXE&JDBC&MyBatis注入环境搭建Hello-Java-SecJavaSecJava安全 - SQL注入-JDBC&MyBatisJDBC注入原理语句拼接预编译的错误使用JdbcTemplate正则过滤MyBatis注入原理Like注入Order B…