当前位置：首页 > news >正文

【数学建模】动态规划算法(Dynamic Programming，简称DP)详解与应用

news 来源：原创 2025/7/5 10:24:55

动态规划算法详解与应用

文章目录

动态规划算法详解与应用
- 引言
- 动态规划的基本概念
- 动态规划的设计步骤
- 经典动态规划问题
- - 1. 斐波那契数列
  - 2. 背包问题
  - 3. 最长公共子序列(LCS)
- 动态规划的优化技巧
- 动态规划的应用领域
- 总结

引言

动态规划(Dynamic Programming，简称DP)是一种解决复杂问题的算法思想，通过将原问题分解为相对简单的子问题，并存储子问题的解来避免重复计算，从而提高算法效率。本文将深入介绍动态规划的基本概念、设计步骤以及经典应用案例。

动态规划的基本概念

动态规划算法通常适用于具有以下特征的问题：

最优子结构：问题的最优解包含子问题的最优解
重叠子问题：在求解过程中，相同的子问题会被多次计算
无后效性：后面的决策不会影响前面的状态

动态规划的设计步骤

设计动态规划算法通常遵循以下步骤：

定义状态：明确定义子问题和状态
确定状态转移方程：找出状态之间的递推关系
确定初始状态和边界条件
确定计算顺序：通常是自底向上或自顶向下
计算最终结果

经典动态规划问题

1. 斐波那契数列

最简单的动态规划例子，定义如下：

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2), n > 1

朴素递归解法（存在重复计算）：

int fib(int n) {if (n <= 1) return n;return fib(n-1) + fib(n-2);
}

动态规划解法：

int fib(int n) {if (n <= 1) return n;int dp[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];
}

2. 背包问题

背包问题

0-1背包问题：有 $N$ 件物品和一个容量为 $V$ 的背包。第i件物品的重量是 $w [i]$ ，价值是 $v [i]$ 。求解将哪些物品装入背包可使价值总和最大。

状态定义： $d p [i] [j]$ 表示前 $i$ 个物品放入容量为 $j$ 的背包的最大价值

状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])  (当j >= w[i])
dp[i][j] = dp[i-1][j]  (当j < w[i])

代码实现：

int knapsack(int W, int w[], int v[], int n) {int dp[n+1][W+1];// 初始化for (int i = 0; i <= n; i++) {for (int j = 0; j <= W; j++) {if (i == 0 || j == 0)dp[i][j] = 0;else if (w[i-1] <= j)dp[i][j] = max(v[i-1] + dp[i-1][j-w[i-1]], dp[i-1][j]);elsedp[i][j] = dp[i-1][j];}}return dp[n][W];
}

3. 最长公共子序列(LCS)

给定两个序列 $X$ 和 $Y$ ，找出它们的最长公共子序列。

状态定义： $d p [i] [j]$ 表示 $X$ 的前 $i$ 个字符与 $Y$ 的前 $j$ 个字符的LCS长度

状态转移方程：

dp[i][j] = dp[i-1][j-1] + 1  (当X[i] == Y[j])
dp[i][j] = max(dp[i-1][j], dp[i][j-1])  (当X[i] != Y[j])

代码实现：

int lcs(string X, string Y) {int m = X.length();int n = Y.length();int dp[m+1][n+1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0)dp[i][j] = 0;else if (X[i-1] == Y[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[m][n];
}

动态规划的优化技巧

空间优化：很多DP问题可以通过滚动数组优化空间复杂度，如0-1背包问题可以优化为一维数组
记忆化搜索：自顶向下的实现方式，结合递归和备忘录
状态压缩：当状态较少时，可以使用位运算压缩状态

动态规划的应用领域

计算机算法：字符串匹配、图论问题
机器学习：隐马尔可夫模型、维特比算法
生物信息学：序列比对
运筹学：资源分配、路径规划

总结

动态规划是一种强大的算法设计技术，通过将复杂问题分解为简单子问题并存储中间结果，有效地解决了许多优化问题。掌握动态规划思想需要大量练习，建议从简单问题入手，逐步提高解题能力。

在实际编程中，动态规划的思想远比具体的代码实现更为重要，关键在于找到问题的状态定义和转移方程。

如有问题或建议，欢迎在评论区留言交流！

【数学建模】动态规划算法(Dynamic Programming，简称DP)详解与应用

动态规划算法详解与应用文章目录动态规划算法详解与应用引言动态规划的基本概念动态规划的设计步骤经典动态规划问题1. 斐波那契数列2. 背包问题3. 最长公共子序列(LCS) 动态规划的优化技巧动态规划的应用领域总结引言动态规划(Dynamic Programming，简称DP)是一…...

编程日记 2025/7/5 10:24:55

UE学习记录part11

第14节 breakable actors 147 destructible meshes a geometry collection is basically a set of static meshes that we get after we fracture a mesh. 几何体集合基本上是我们在断开网格后获得的一组静态网格。选中要破碎的网格物品，创建集合可以选择不同的…...

编程日记 2025/7/5 10:05:29

1、Scanner 输入： import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取整数int num scanner.nextInt();// 读取一行字符串String line scanner.nextLine();scanner.close();…...

编程日记 2025/7/5 10:13:12

浅析车规芯片软错误防护加固的重要性

随着汽车电子技术的飞速发展，汽车已经从传统的机械交通工具转变为高度依赖电子系统的智能移动终端。车规芯片作为汽车电子系统的核心部件，其可靠性和安全性直接关系到车辆的正常运行和驾乘人员的安全。然而，车规芯片在复杂的运行环境中面临着…...

编程日记 2025/7/5 9:54:39

Android Jetpack学习总结（源码级理解）

ViewModel 和 LiveData 是 Android Jetpack 组件库中的两个核心组件，它们能帮助开发者更有效地管理 UI 相关的数据，并且能够在配置变更（如屏幕旋转）时保存和恢复 UI 数据。 ViewModel作用瞬态数据丢失的恢复，比如横竖…...

编程日记 2025/7/5 8:58:22

Matlab_Simulink中导入CSV数据与仿真实现方法

前言在Simulink仿真中，常需将外部数据（如CSV文件或MATLAB工作空间变量）作为输入信号驱动模型。本文介绍如何高效导入CSV数据至MATLAB工作空间，并通过From Workspace模块实现数据到Simulink的精确传输，适用于运动控制…...

编程日记 2025/7/5 8:37:30

Go 语言规范学习（6）

文章目录 StatementsTerminating statementsEmpty statementsLabeled statementsExpression statementsSend statementsIncDec statementsAssignment statementsIf statementsSwitch statementsExpression switchesType switches For statementsFor statements with single con…...

编程日记 2025/7/5 9:50:18

设计模式——设计模式理念

文章目录参考：[设计模式——设计模式理念](https://mp.weixin.qq.com/s/IEduZFF6SaeAthWFFV6zKQ)参考：[设计模式——工厂方法模式](https://mp.weixin.qq.com/s/7tKIPtjvDxDJm4uFnqGsgQ)参考：[设计模式——抽象工厂模式](https://mp.weixin.…...

编程日记 2025/7/5 8:58:22

解析 ID 数组传参的解决方案：基于 Axios 的实现

解析 ID 数组传参的解决方案：基于 Axios 的实现在实际开发中，经常需要将一个 ID 数组作为参数传递给后端接口。然而，不同的后端框架和前端库对数组参数的处理方式可能有所不同。通过一个具体的例子，在前端使用 Axios 框架发送 I…...

编程日记 2025/7/5 7:41:11

C语言快速入门-C语言基础知识

这个c语言入门，目标人群是有代码基础的，例如你之前学过javaSE，看此文章可能是更有帮助，会让你快速掌握他们之间的差异，文章内容大部分都是泛谈，详细的部分我会在之后时间发布，我也在慢慢学习&am…...

编程日记 2025/7/5 7:25:37

Ubuntu 22.04 上安装 VS Code

在 Ubuntu 22.04 上安装 VS Code 的方法如下： 方法 1：通过 APT 包管理器安装更新系统包索引： 打开终端并执行以下命令： sudo apt update安装依赖项： 执行以下命令以安装所需的依赖项： sudo apt install s…...

编程日记 2025/7/5 7:08:41

AI人工智能-PyCharm的介绍安装应用

下载与安装创建python项目项目路径：C:\Users\miloq\Desktop\python_project 配置环境提前找到conda配置的python-base路径配置conda环境运行项目运行结果...

编程日记 2025/7/5 8:16:17

Todesk介绍

文章目录 ToDesk 软件介绍1. 软件概述2. ToDesk 的功能特点2.1 简单易用2.2 高质量的图像与流畅的操作2.3 跨平台支持2.4 多屏显示与协作2.5 文件传输功能2.6 实时聊天与语音通话2.7 远程唤醒与自动启动2.8 多种权限设置与安全性2.9 无需公网 IP 3. ToDesk 的应用场景3.1 个人使…...

编程日记 2025/7/5 7:07:55

【JavaEE】springMVC返回Http响应

目录一、返回页面二、Controller和ResponseBody与RestController区别三、返回HTML代码⽚段四、返回JSON五、HttpServletResponse设置状态码六、设置Header6.1 HttpServletResponse设置6.2 RequestMapping设置一、返回页面步骤如下： 我们先要在static目录下创建…...

编程日记 2025/7/5 7:48:12

青少年编程与数学 02-011 MySQL数据库应用 02课题、MySQL数据库安装

青少年编程与数学 02-011 MySQL数据库应用 02课题、MySQL数据库安装一、安装Windows系统Linux系统（以Ubuntu 20.04为例）macOS系统二、配置（一）Windows系统1. 创建配置文件2. 初始化数据库3. 启动MySQL服务4. 登录MySQL5. 修改ro…...

编程日记 2025/7/5 8:10:04

springboot441-基于SpringBoot的校园自助交易系统(源码+数据库+纯前后端分离+部署讲解等)

💕💕作者： 爱笑学姐 💕💕个人简介：十年Java，Python美女程序员一枚，精通计算机专业前后端各类框架。 💕💕各类成品Java毕设。javaweb，ssm&#xf…...

编程日记 2025/7/5 8:19:29

【安全运营】关于攻击面管理相关概念的梳理（一）

目录一、ASM 介绍ASM 是“Attack Surface Management”（攻击面管理）的缩写【框架视角，广义概念】1. 介绍2. 兴起的原因3. 工作流程3.1 资产发现3.2 分类和优先级排序3.3 修复3.4 监控二、EASM 介绍EASM 是 "External Attack Surface M…...

编程日记 2025/7/5 8:30:35

IPv6 网络访问异常 | 时好时坏 / 部分访问正常

注：本文为 “ IPv6 间接性连接异常” 相关文章合辑。略作重排，未去重。如有内容异常，请看原文。 IPv6 间接性连接异常？尝试调整路由器的 MTU 设置 Nero978 2024-1-29 17:54 背景 2024 年 1 月 29 日，因寒假返家…...

编程日记 2025/7/5 7:24:08

Unity编辑器功能及拓展(1) —特殊的Editor文件夹

Unity中的Editor文件夹是一个具有特殊用途的目录，主要用于存放与编辑器扩展功能相关的脚本和资源。一.纠缠不清的UnityEditor 我们Unity中进行游戏构建时，我们经常遇到关于UnityEditor相关命名空间丢失的报错，这时候，只得将报错…...

编程日记 2025/7/5 7:41:59

LLMs之PE：《Tracing the thoughts of a large language model》翻译与解读

LLMs之PE：《Tracing the thoughts of a large language model》翻译与解读导读：这篇论文的核心贡献在于提出了一种新颖的、基于提示工程的LLMs推理过程追踪技术——“Tracing Thoughts”。该技术通过精心设计的提示，引导LLMs生成其推理过程的…...

编程日记 2025/7/5 8:34:14

[Python] 贪心算法简单版

贪心算法-简单版贪心算法的一般使用场景是给定一个列表ls, 让你在使用最少的数据的情况下达到或超过n. 我们就来使用上面讲到的这个朴素的例题来讲讲贪心算法的基本模板: 2-1.排序既然要用最少的数据, 我们就要优先用大的数据拼, 为了实现这个效果, 我们得先给列表从大到小…...

编程日记 2025/7/5 7:26:22

游戏引擎学习第191天

回顾并制定今天的计划最近几天，我们有一些偏离了原计划的方向，主要是开始了一些调试代码的工作。最初我们计划进行一些调试功能的添加，但是随着工作的深入，我们开始清理和整理调试界面的呈现方式，以便能够做一些更复…...

编程日记 2025/7/5 7:39:11

Git撤回操作全场景指南：未推送与已推送，保留和不保留修改的差异处理

一、未推送到远程仓库的提交（仅本地存在） 特点：可直接修改本地提交历史，不会影响他人 1. 保留修改重新提交 git reset --soft HEAD~1 # 操作效果： # - 撤销最后一次提交 # - 保留工作区所有修改 # - 暂存区内容保持…...

编程日记 2025/7/5 7:50:27

Java 贪吃蛇游戏

这段 Java 代码实现了一个经典的贪吃蛇游戏。玩家可以使用键盘的上下左右箭头键控制蛇的移动方向，蛇会在游戏面板中移动并尝试吃掉随机生成的食物。每吃掉一个食物，蛇的身体会变长，玩家的得分也会增加。如果蛇撞到自己的身体或者撞到游戏面板…...

编程日记 2025/7/5 7:37:40

QT图片轮播器(QT实操学习2)

1.项目架构 1.UI界面 2.widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget>#define TIMEOUT 1 * 1000 QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent n…...

编程日记 2025/7/5 7:28:43

mac m1/m2/m3 pyaudio的安装

google了很多方法，也尝试了 issue68的方法， 但是均失败了，但是问deepseek竟然成功了，下面是deepseek r1给出的方法。在M3 pro芯片上可以成功运行. 安装homebrew /bin/bash -c "$(curl -fsSL https://raw.githubusercontent…...

编程日记 2025/7/5 7:09:33

Appium中元素定位的注意点

应用场景了解这些注意点可以以后在出错误的时候，更快速的定位问题原因。示例使用 find_element_by_xx 或 find_elements_by_xx 的方法，分别传入一个没有的“特征“会是什么结果呢? 核心代码 driver.find_element_by_id("xxx") drive…...

编程日记 2025/7/5 7:58:42

《深入探索 Python 数据分析：用 Pandas 高效处理与可视化大型数据集》

《深入探索 Python 数据分析：用 Pandas 高效处理与可视化大型数据集》引言：从零到分析高手数据是当代社会最宝贵的资源，而数据分析技能是现代职业人不可或缺的一部分。在数据科学的领域中，Python 已成为当之无愧的“首选语言”，其强大的生态系统和简洁的语法让人如虎添…...

编程日记 2025/7/5 8:10:45

[GWCTF 2019]我有一个数据库1 [CVE phpMyAdmin漏洞]

扫出来一些东西访问/phpmyadmin 发现界面这里用到了CVE-2018-12613，光速学习出现漏洞的代码是： $target_blacklist array (import.php, export.php );// If we have a valid target, lets load that script instead if (! empty($_REQUEST[targe…...

编程日记 2025/7/1 14:53:56

spring 常用注解区别及使用场景

1. 组件注册注解 Bean 作用：用于方法上，表示该方法返回的对象由Spring容器管理。通常用于配置类（Configuration）中，注册第三方库或自定义的Bean。使用场合： 当你需要将非Spring管理的类（如第…...

编程日记 2025/7/2 8:44:22

【后端】【Django】信号使用详解

Django post_save 信号使用详解（循序渐进） 一、信号的基本概念 Django 的信号（Signal） 允许不同部分的代码在发生某些事件时进行通信，而不需要直接调用。这种机制可以解耦代码，让不同的模块独立工作。 …...

编程日记 2025/7/2 1:34:33

ML算法数学概念

交叉熵损失（Cross-Entropy Loss） 是机器学习和深度学习中常用的一种损失函数，主要用于衡量两个概率分布之间的差异。它在分类问题中（尤其是多分类问题）被广泛使用，因为它能够有效地评估模型预测的概率分布与…...

编程日记 2025/7/4 12:27:16

wps 怎么显示隐藏文字

wps 怎么显示隐藏文字》文件》选项》视图》勾选“隐藏文字” wps怎么设置隐藏文字 wps怎么设置隐藏文字...

编程日记 2025/6/28 6:23:34

Vue3 其它API Teleport 传送门

Vue3 其它API Teleport 传送门在定义一个模态框时，父组件的filter属性会影响子组件的position属性，导致模态框定位错误使用Teleport解决这个问题把模态框代码传送到body标签下...

编程日记 2025/6/28 6:37:48

亚马逊玩具品类技术驱动型选品策略：从趋势洞察到合规基建

一、全球玩具电商技术演进趋势 （技术化重构原市场背景） 数据可视化分析：通过亚马逊SP-API抓取2023年玩具品类GMV分布热力图监管技术升级： 美国CPSC启用AI质检系统（缺陷识别准确率92.7%） 欧盟EPR合规接口…...

编程日记 2025/6/28 3:01:59

SpringBoot3+EasyExcel通过WriteHandler动态实现表头重命名

方案简介为了通过 EasyExcel 实现动态表头重命名，可以封装一个方法，传入动态的新表头名称列表（List<String>），并结合 WriteHandler 接口来重命名表头。同时，通过 EasyExcel 将数据直接写入到输出流…...

编程日记 2025/7/3 13:03:44

PHY——LAN8720A 寄存器读写 (二)

文章目录 PHY——LAN8720A 寄存器读写 (二)工程配置引脚初始化代码以太网初始化代码PHY 接口实现LAN8720 接口实现PHY 接口测试 PHY——LAN8720A 寄存器读写 (二) 工程配置这里以野火电子的 F429 开发板为例，配置以太网外设这里有一点需要注意原理图 RMII_TXD0…...

编程日记 2025/7/1 4:43:56

HTML5和CSS3的一些特性

HTML5 和 CSS3 是现代网页设计的基础技术，它们引入了许多新特性和功能，极大地丰富了网页的表现力和交互能力。 HTML5 的一些重要特性包括： 新的语义化标签: HTML5 引入了一些重要的语义化标签如 <header>, <footer>, <articl…...

编程日记 2025/6/28 5:21:57

sass报错，忽略 Sass 弃用警告，降级版本

最有效的方法是创建一个 .sassrc.json 文件来配置 Sass 编译器。告诉 Sass 编译器忽略来自依赖项的警告消息。解决方案： 1. 在项目根目录创建 .sassrc.json 文件： {"quietDeps": true }这个配置会让 Sass 编译器忽略所有来自依赖项&#x…...

编程日记 2025/6/29 11:55:00

DeepSeek+Kimi：PPT制作的效率革命

摘要：传统PPT制作面临模板选择困难、内容逻辑混乱、设计排版能力有限以及反复修改等问题。DeepSeek和Kimi两款AI工具的组合为PPT制作提供了全新的解决方案。DeepSeek擅长内容生成与逻辑推理，能够快速生成高质量的PPT大纲和内容；Kimi则专注于长…...

编程日记 2025/7/2 20:05:40

transformers中学习率warmup策略具体如何设置

在使用 get_linear_schedule_with_warmup（如 Hugging Face Transformers 库中的学习率调度器）时，参数的合理设置需要结合数据量（dataset size）、批次大小（batch size） 和训练轮数（…...

编程日记 2025/7/5 8:51:32

linux实现rsync+sersync实时数据备份

1.概述 rsync(Remote Sync) 是一个Unix/linux系统下的文件同步和传输工具 2.端口和运行模式 tcp/873 采用C/S模式（客户端/服务器模式） 3.特点可以镜像保存整个目录和文件第一次全量备份(备份全部的文件),之后是增量备份(只备份变化的文件) 4. 数…...

编程日记 2025/7/1 4:45:29

CTF类题目复现总结-[MRCTF2020]ezmisc 1

一、题目地址 https://buuoj.cn/challenges#[MRCTF2020]ezmisc二、复现步骤 1、下载附件，得到一张图片； 2、利用010 Editor打开图片，提示CRC值校验错误，flag.png应该是宽和高被修改了，导致flag被隐藏掉；…...

编程日记 2025/7/3 18:01:21

『Linux』第十一章线程同步与互斥

1. 线程互斥 1.1 进程线程间的互斥相关背景概念临界资源：多线程执行流共享的资源就叫做临界资源临界区：每个线程内部，访问临界资源的代码，就叫做临界区互斥：任何时刻，互斥保证有且只有一个执行流进入临界…...

编程日记 2025/7/3 7:25:18

【数据结构】队列

目录一、队列1、概念与结构2、队列的实现3、队列的初始化4、打印队列数据5、入队6、销毁队列7、队列判空8、出队9、取队头、队尾数据10、队列中有效元素个数二、源码个人主页，点击这里~ 数据结构专栏，点击这里~ 一、队列 1、概念与结构概念&#x…...

编程日记 2025/6/28 4:58:00

【导航定位】GNSS数据协议-RINEX OBS

RINEX协议 RINEX(Receiver INdependent EXchange format,与接收机无关的交换格式)是一种在GPS测量应用中普遍采用的标准数据格式,该格式采用文本文件形式（ASCII码）存储数据数据记录格式与接收机的制造厂商和具体型号无关。目前RINEX版本已经发布到了4.x…...

编程日记 2025/6/27 21:05:59

Qt中的事件循环

Qt的事件循环是其核心机制之一，它是一种消息处理机制，负责处理各种事件(如用户输入、定时器、网络请求等)的分发和处理。Qt中的事件循环是一个持续运行的循环，负责接收事件并将它们分发给相应的对象进行处理。当没有事件需要处理时&#xff0…...

编程日记 2025/7/5 9:18:01

Android并发编程：线程池与协程的核心区别与最佳实践指南

1. 基本概念对比特性线程池 (ThreadPool) 协程 (Coroutine) 本质 Java线程管理机制 Kotlin轻量级并发框架最小执行单元线程(Thread) 协程(Coroutine) 创建开销较高(需分配系统线程资源) 极低(用户态调度) 并发模型基于线程的抢占式调度基于协程的协作式调度 2. 核心差异…...

编程日记 2025/7/3 19:23:51