动态规划 详解

news/2024/11/26 9:00:24/

动态规划(Dynamic Programming, DP)详解

动态规划是一种通过分解问题为子问题并利用子问题的解来解决原问题的算法设计方法。它通常用于解决具有 重叠子问题最优子结构 性质的问题。


1. 动态规划的核心思想

1.1 重叠子问题

  • 问题可以分解为多个子问题,且这些子问题会重复出现。
  • 动态规划通过 记忆化(Memoization)表格(Tabulation) 的方式保存子问题的解,避免重复计算。

示例:斐波那契数列

  • 递归法会重复计算大量子问题,如:
    F ( 5 ) = F ( 4 ) + F ( 3 ) F(5) = F(4) + F(3) F(5)=F(4)+F(3)
    其中:
    F ( 4 ) = F ( 3 ) + F ( 2 ) F(4) = F(3) + F(2) F(4)=F(3)+F(2)
    可以看到,F(3) 被重复计算。

1.2 最优子结构

  • 一个问题的最优解可以通过其子问题的最优解推导得到。
  • 如果问题不满足最优子结构,动态规划无法使用。

示例:最短路径问题

  • 若从点 A 到点 C 的最短路径经过点 B,则从 A 到 B 和 B 到 C 的路径也必须是最短的。

1.3 状态转移

  • 动态规划通过状态转移方程来定义子问题之间的关系。

示例:斐波那契数列

  • 递归公式(状态转移方程): F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n-1) + F(n-2) F(n)=F(n1)+F(n2)

2. 动态规划的解题步骤

动态规划一般按照以下步骤来解决问题:

2.1 明确状态

  • 定义一个数组或变量表示问题的状态。
  • 状态表示动态规划的核心,通常需要回答:
    • 子问题是什么?
    • 如何通过状态表示子问题?

示例:最长上升子序列

  • 状态定义:dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。

2.2 确定状态转移方程

  • 状态转移方程描述了当前状态如何由之前的状态推导而来。

示例:最长上升子序列

  • 转移方程:若第 i 个元素大于第 j 个元素:
    d p [ i ] = max ⁡ ( d p [ i ] , d p [ j ] + 1 ) ( j < i ) dp[i] = \max(dp[i], dp[j] + 1) \quad (j < i) dp[i]=max(dp[i],dp[j]+1)(j<i)

2.3 初始化

  • 为边界状态赋初值,通常与问题的初始条件对应。

示例:最长上升子序列

  • 初始状态:每个元素单独构成一个序列:
    d p [ i ] = 1 dp[i] = 1 dp[i]=1

2.4 计算顺序

  • 通过遍历、递推等方法计算所有子问题的解。
  • 通常选择从小到大的顺序来保证子问题已经被计算。

2.5 返回最终结果

  • 根据问题要求返回最终结果,通常是 dp 数组中的某个值或整体。

3. 动态规划的两种实现方式

3.1 自顶向下(记忆化递归)

  • 类似于递归,将大问题分解为小问题,先解决需要的子问题。
  • 使用缓存(如数组或哈希表)保存已计算过的子问题结果。

示例:斐波那契数列

public class Fibonacci {private static int[] memo;public static int fib(int n) {if (n <= 1) return n;// 检查是否已经计算过if (memo[n] != -1) return memo[n];// 递归计算,并存储结果memo[n] = fib(n - 1) + fib(n - 2);return memo[n];}public static void main(String[] args) {int n = 10;memo = new int[n + 1];Arrays.fill(memo, -1);System.out.println(fib(n)); // 输出:55}
}

3.2 自底向上(迭代法)

  • 先解决最小子问题,再逐步推导大问题。
  • 使用表格存储子问题的解,按顺序填表。

示例:斐波那契数列

public class Fibonacci {public static 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];}public static void main(String[] args) {System.out.println(fib(10)); // 输出:55}
}

4. 动态规划的分类

4.1 一维动态规划

  • 问题状态只与一个变量有关。
  • 例子:斐波那契数列、爬楼梯问题。

4.2 二维动态规划

  • 问题状态与两个变量有关(如二维表格问题)。
  • 例子:最长公共子序列(LCS)、编辑距离(Levenshtein Distance)。

4.3 背包问题

  • 0-1 背包问题: 选择每个物品时要么拿,要么不拿。
  • 完全背包问题: 每个物品可以选无限次。
  • 多重背包问题: 每个物品有一个选择次数限制。

4.4 区间动态规划

  • 问题状态与区间的起点和终点有关。
  • 例子:矩阵链乘法、戳气球问题。

4.5 状态压缩动态规划

  • 用位运算压缩多个状态。
  • 例子:旅行商问题(TSP)。

5. 常见动态规划问题及解法

5.1 斐波那契数列

状态转移方程:
F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n-1) + F(n-2) F(n)=F(n1)+F(n2)


5.2 爬楼梯问题

  • 每次可以爬 1 或 2 个台阶,求到达第 n 级台阶的总方法数。
    状态转移方程:
    d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i-1] + dp[i-2] dp[i]=dp[i1]+dp[i2]

5.3 最长公共子序列

  • 给定两个字符串,求它们的最长公共子序列。
    状态转移方程:
    d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] + 1 if  A [ i ] = B [ j ] max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) otherwise dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } A[i] = B[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases} dp[i][j]={dp[i1][j1]+1max(dp[i1][j],dp[i][j1])if A[i]=B[j]otherwise

5.4 0-1 背包问题

  • 给定物品重量和价值,选择部分物品放入背包,最大化总价值。
    状态转移方程:
    d p [ i ] [ w ] = max ⁡ ( d p [ i − 1 ] [ w ] , d p [ i − 1 ] [ w − weight [ i ] ] + value [ i ] ) dp[i][w] = \max(dp[i-1][w], dp[i-1][w-\text{weight}[i]] + \text{value}[i]) dp[i][w]=max(dp[i1][w],dp[i1][wweight[i]]+value[i])

6. 总结

动态规划的核心是通过分治和记忆化避免重复计算,适用于具有 重叠子问题最优子结构 的问题。以下是使用动态规划时需要注意的关键点:

  1. 确定状态表示和状态转移方程。
  2. 明确子问题之间的依赖关系。
  3. 选择合适的实现方式(递归+记忆化 或 迭代+表格)。
  4. 对问题规模和时间复杂度进行优化(如滚动数组优化空间复杂度)。

http://www.ppmy.cn/news/1550017.html

相关文章

【C语言】野指针问题详解及防范方法

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C语言 文章目录 &#x1f4af;前言&#x1f4af;什么是野指针&#xff1f;&#x1f4af;未初始化的指针代码示例问题分析解决方法 &#x1f4af;指针越界访问代码示例问题分析解决方法 &#x1f4af;指向已释放内存的…

navicat密码解密python

其他资料都是用php写的&#xff0c;但是运行起来好像有点问题&#xff0c;提供python代码&#xff0c;首先注册表获取加密后的密码&#xff0c;然后运行下述代码解密。 参考&#xff1a;获取navicat密码 import hashlib from Crypto.Cipher import AES, Blowfish from Crypto.…

内存不足引发C++程序闪退崩溃问题的分析与总结

目录 1、内存不足一般出现在32位程序中 2、内存不足时会导致malloc或new申请内存失败 2.1、malloc申请内存失败&#xff0c;返回NULL 2.2、new申请内存失败&#xff0c;抛出异常 3、内存不足项目实战案例中相关细节与要点说明 3.1、内存不足导致malloc申请内存失败&#…

【Pytest+Yaml+Allure】实现接口自动化测试框架

一、框架思想 requestsyamlpytestallure实现接口自动化框架。结合数据驱动和分层思想&#xff0c;将代码与数据分离&#xff0c;易维护&#xff0c;易上手。使用yaml编写编写测试用例&#xff0c;利用requests库发送请求&#xff0c;使用pytest管理用例&#xff0c;allure生成…

Linux常用指令(1)

目录 何为指令 基本常用指令 1.clear 2.exit 3.whoami 4.pwd 5.which 6.alias 7.tree ls指令 pwd指令 cd指令 touch指令 mkdir指令 rmdir指令 && rm指令 rmdir指令 rm指令 man指令 cp指令 何为指令 指令的本质其实就是可执行程序。 指令 可执行文件…

第十章 作业

在网页中显示一个工作中的“数字时钟” <!DOCTYPE html> <html><head><meta charset"utf-8"><title>动态时钟</title><style>.all{width: 600px;height: 300px;margin: 100px auto;text-align: center;font-size: 50px;}…

(vue)el-tag标签展开收起效果实现

(vue)el-tag标签展开收起效果实现 效果&#xff1a; 收起: 展开&#xff1a; 实现方法 父组件 <el-form-item class"historay-form-item" label"历史文件"><UploadList ref"uploadListRef" /> </el-form-item><script…

rabbitmq exchange queue topic的关系

在RabbitMQ中&#xff0c;Exchange、Queue 和 Topic 是三个核心概念&#xff0c;它们之间有着密切的关系。理解这些概念及其相互作用对于正确使用RabbitMQ非常重要。下面是对这三个概念的详细解释以及它们之间的关系&#xff1a; 1. Exchange&#xff08;交换器&#xff09; …