动态规划详解：从入门到精通

Ne0inhk

— 8 min read

摘要

动态规划（Dynamic Programming，DP）是算法设计中的一种重要思想，广泛应用于各类优化问题。本文将深入讲解动态规划的基本概念、核心要素、解题步骤和经典问题。我们将通过背包问题、爬楼梯问题、编辑距离等经典案例，详细介绍动态规划的思维过程和实现方法。文章包含丰富的图示和Python代码示例，帮助读者掌握动态规划的精髓，提升算法设计和问题解决能力。

正文

1. 引言

动态规划是解决具有重叠子问题和最优子结构性质问题的一种算法设计技术。它将复杂问题分解为更小的子问题，通过保存子问题的解来避免重复计算，从而提高算法效率。动态规划广泛应用于最优化问题，如资源分配、路径规划、序列比对等领域。

2. 动态规划基本概念

2.1 核心要素

动态规划问题通常具有以下三个核心要素：

  1. 重叠子问题：问题可以分解为相互重叠的子问题
  2. 最优子结构：问题的最优解包含子问题的最优解
  3. 无后效性：某阶段状态一旦确定，不受这个状态以后决策的影响
2.2 解题步骤

使用动态规划解决问题通常包括以下步骤：

  1. 定义状态：确定用哪些变量表示问题的状态
  2. 状态转移方程：找出状态之间的递推关系
  3. 初始化：确定初始状态的值
  4. 计算顺序：确定状态的计算顺序
  5. 返回结果：根据计算结果返回最终答案

3. 经典动态规划问题

3.1 0-1背包问题

0-1背包问题是动态规划的经典问题之一。给定一个容量为cap的背包和n个物品，每个物品有重量wgt[i]和价值val[i]，要求在不超过背包容量的前提下，使装入背包的物品总价值最大。

暴力搜索解法
defknapsack_dfs(wgt:list[int], val:list[int], i:int, c:int)->int:"""0-1 背包：暴力搜索"""# 若已选完所有物品或背包无剩余容量，则返回价值 0if i ==0or c ==0:return0# 若超过背包容量，则只能选择不放入背包if wgt[i -1]> c:return knapsack_dfs(wgt, val, i -1, c)# 计算不放入和放入物品 i 的最大价值 no = knapsack_dfs(wgt, val, i -1, c) yes = knapsack_dfs(wgt, val, i -1, c - wgt[i -1])+ val[i -1]# 返回两种方案中价值更大的那一个returnmax(no, yes)
记忆化搜索优化
defknapsack_dfs_mem( wgt:list[int], val:list[int], mem:list[list[int]], i:int, c:int)->int:"""0-1 背包：记忆化搜索"""# 若已选完所有物品或背包无剩余容量，则返回价值 0if i ==0or c ==0:return0# 若已有记录，则直接返回if mem[i][c]!=-1:return mem[i][c]# 若超过背包容量，则只能选择不放入背包if wgt[i -1]> c:return knapsack_dfs_mem(wgt, val, mem, i -1, c)# 计算不放入和放入物品 i 的最大价值 no = knapsack_dfs_mem(wgt, val, mem, i -1, c) yes = knapsack_dfs_mem(wgt, val, mem, i -1, c - wgt[i -1])+ val[i -1]# 记录并返回两种方案中价值更大的那一个 mem[i][c]=max(no, yes)return mem[i][c]
动态规划解法
defknapsack_dp(wgt:list[int], val:list[int], cap:int)->int:"""0-1 背包：动态规划""" n =len(wgt)# 初始化 dp 表 dp =[[0]*(cap +1)for _ inrange(n +1)]# 状态转移for i inrange(1, n +1):for c inrange(1, cap +1):if wgt[i -1]> c:# 若超过背包容量，则不选物品 i dp[i][c]= dp[i -1][c]else:# 不选和选物品 i 这两种方案的较大值 dp[i][c]=max(dp[i -1][c], dp[i -1][c - wgt[i -1]]+ val[i -1])return dp[n][cap]defknapsack_dp_comp(wgt:list[int], val:list[int], cap:int)->int:"""0-1 背包：空间优化后的动态规划""" n =len(wgt)# 初始化 dp 表 dp =[0]*(cap +1)# 状态转移for i inrange(1, n +1):# 倒序遍历for c inrange(cap,0,-1):if wgt[i -1]> c:# 若超过背包容量，则不选物品 i dp[c]= dp[c]else:# 不选和选物品 i 这两种方案的较大值 dp[c]=max(dp[c], dp[c - wgt[i -1]]+ val[i -1])return dp[cap]
3.2 爬楼梯问题

爬楼梯问题是另一个经典的动态规划问题。假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶，问有多少种不同的方法可以爬到楼顶。

defclimb_stairs_dp(n:int)->int:"""爬楼梯：动态规划"""if n <=2:return n # 初始化 dp 表，用于存储子问题的解 dp =[0]*(n +1)# 初始状态：已在第 1, 2 阶 dp[1], dp[2]=1,2# 状态转移：从第 3 阶开始for i inrange(3, n +1): dp[i]= dp[i -1]+ dp[i -2]return dp[n]defclimb_stairs_dp_comp(n:int)->int:"""爬楼梯：空间优化后的动态规划"""if n <=2:return n # 仅需存储前两个状态 prev1, prev2 =1,2# 状态转移：从第 3 阶开始for _ inrange(3, n +1): curr = prev1 + prev2 prev1, prev2 = prev2, curr return prev2
3.3 编辑距离问题

编辑距离是衡量两个字符串相似度的重要指标，定义为由一个字符串转换成另一个字符串所需的最少编辑操作次数。

defedit_distance_dp(s:str, t:str)->int:"""编辑距离：动态规划""" n, m =len(s),len(t)# 初始化 dp 表 dp =[[0]*(m +1)for _ inrange(n +1)]# 初始化首行首列for i inrange(1, n +1): dp[i][0]= i for j inrange(1, m +1): dp[0][j]= j # 状态转移for i inrange(1, n +1):for j inrange(1, m +1):if s[i -1]== t[j -1]:# 两字符相等，不需要编辑 dp[i][j]= dp[i -1][j -1]else:# 两字符不相等，取三者中的最小值 dp[i][j]=min( dp[i][j -1]+1,# 插入 dp[i -1][j]+1,# 删除 dp[i -1][j -1]+1# 替换)return dp[n][m]

4. 动态规划优化技巧

4.1 空间优化

在许多动态规划问题中，当前状态只依赖于有限的前几个状态，因此可以优化空间复杂度：

deffibonacci(n:int)->int:"""斐波那契数列：空间优化后的动态规划"""if n <=1:return n # 仅需存储前两个状态 prev1, prev2 =0,1# 状态转移for _ inrange(2, n +1): curr = prev1 + prev2 prev1, prev2 = prev2, curr return prev2
4.2 状态压缩

对于某些二维DP问题，可以通过状态压缩将空间复杂度从O(n²)降低到O(n)：

defmin_path_sum_dp_comp(grid:list[list[int]])->int:"""最小路径和：空间优化后的动态规划""" n, m =len(grid),len(grid[0])# 初始化 dp 表 dp =[0]* m # 初始化首行 dp[0]= grid[0][0]for j inrange(1, m): dp[j]= dp[j -1]+ grid[0][j]# 状态转移for i inrange(1, n):# 首列 dp[0]+= grid[i][0]for j inrange(1, m): dp[j]=min(dp[j], dp[j -1])+ grid[i][j]return dp[m -1]

5. 动态规划与其他算法的结合

5.1 动态规划与贪心算法

在某些问题中，贪心算法可以看作是动态规划的一种特殊情况：

defcoin_change_greedy(coins:list[int], amt:int)->int:"""零钱兑换：贪心"""# 假设 coins 列表有序 i =len(coins)-1 count =0# 循环进行贪心选择，直到无剩余金额while amt >0:# 找到小于且最接近剩余金额的硬币while i >0and coins[i]> amt: i -=1# 选择 coins[i] amt -= coins[i] count +=1# 若未找到可行方案，则返回 -1return count if amt ==0else-1defcoin_change_dp(coins:list[int], amt:int)->int:"""零钱兑换：动态规划"""# 初始化 dp 表 dp =[amt +1]*(amt +1) dp[0]=0# 状态转移for coin in coins:for a inrange(coin, amt +1): dp[a]=min(dp[a], dp[a - coin]+1)return dp[amt]if dp[amt]!= amt +1else-1

6. 实践案例

在实际应用中，动态规划广泛应用于各种场景：

# 股票买卖问题defmax_profit(prices:list[int])->int:"""买卖股票的最佳时机"""ifnot prices:return0 min_price = prices[0] max_profit =0for price in prices[1:]: min_price =min(min_price, price) max_profit =max(max_profit, price - min_price)return max_profit # 最长公共子序列deflongest_common_subsequence(text1:str, text2:str)->int:"""最长公共子序列：动态规划""" n, m =len(text1),len(text2)# 初始化 dp 表 dp =[[0]*(m +1)for _ inrange(n +1)]# 状态转移for i inrange(1, n +1):for j inrange(1, m +1):if text1[i -1]== text2[j -1]: dp[i][j]= dp[i -1][j -1]+1else: dp[i][j]=max(dp[i -1][j], dp[i][j -1])return dp[n][m]

总结

动态规划是一种强大的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。掌握动态规划的关键在于：

  1. 识别问题特征：判断问题是否适合用动态规划解决
  2. 定义状态：合理定义状态表示问题的子结构
  3. 建立状态转移方程：找出状态之间的递推关系
  4. 优化实现：通过空间优化等技巧提高算法效率

通过大量练习和实践，我们可以逐步掌握动态规划的精髓，在面对复杂问题时能够灵活运用这一重要算法思想。

参考资料

  1. Hello 算法项目: https://www.hello-algo.com/
  2. 《算法导论》第三版
  3. 《算法竞赛入门经典》
  4. LeetCode算法题库: https://leetcode.com/

Read more

使用Docker安装Ollama及Open-WebUI完整教程

作者：吴业亮 博客：wuyeliang.blog.ZEEKLOG.net 一、Ollama 简介及工作原理 1. Ollama 简介及原理 * 简介：Ollama 是一款轻量级、开源的大语言模型（LLM）运行工具，旨在简化本地部署和运行大语言模型的流程。它支持 Llama 3、Mistral、Gemini 等主流开源模型，用户无需复杂配置即可在本地设备（CPU 或 GPU）上快速启动模型，适用于开发测试、本地智能应用搭建等场景。 * 工作原理： * 采用模型封装机制，将大语言模型的运行环境、依赖库及推理逻辑打包为标准化格式，实现模型的一键下载、启动和版本管理。 * 通过优化的推理引擎适配硬件架构，支持 CPU 基础运行和 GPU 加速（如 NVIDIA CUDA），减少资源占用并提升响应速度。 * 提供简洁的

By Ne0inhk
根据设计图生成前端代码，零基础入门到精通，收藏这篇就够了

根据设计图生成前端代码，零基础入门到精通，收藏这篇就够了

在现代前端开发中，从设计稿到可用页面的交付往往需要大量重复劳动：切图、手写样式、布局调整……而借助 MCP Server - Figma AI Bridge，我们可以将 Figma 设计稿自动转换成整洁的 HTML/CSS/JS 代码，并立即生成可预览的网页。一键化、傻瓜式操作，让设计交付效率跃升。 本文测试使用的系统环境如下： * Trae IDE 版本：2.4.5 * macOS 版本：14.7 * Node.js 版本：24.6.0 * npx 版本：11.5.2 * Python 版本：3.13.3

By Ne0inhk
深入解析WebView的概念、功能、应用场景以及使用过程中的优势与挑战

深入解析WebView的概念、功能、应用场景以及使用过程中的优势与挑战

🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_ZEEKLOG博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》、《前端求职突破计划》 🍚 蓝桥云课签约作者、上架课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入门到实战全面掌握 uni-app》 文章目录 * * 一、引言 * 二、WebView概述 * 三、WebView的功能与应用场景 * 四、WebView的优势与挑战 * 五、WebView的使用示例 * 六、总结 摘要： 本文详细介绍了App中WebView的概念、功能、应用场景以及使用过程中的优势与挑战。通过对WebView的深入剖析，帮助开发者更好地理解和运用这一技术，在App开发中实现更丰富的功能和更好的用户体验。 一、引言 在移动应用开发领域，为了在App中展示网页内容、集成Web应用或实现与网页的交互功能，WebView是一种常用的技术手段。它为开发者提供了一种在原生App中嵌入Web内容的

By Ne0inhk
Web 毕设篇-适合练手的 Spring Boot Web 毕业设计项目：智驿AI系统（前后端源码 + 数据库 sql 脚本）

Web 毕设篇-适合练手的 Spring Boot Web 毕业设计项目：智驿AI系统（前后端源码 + 数据库 sql 脚本）

🔥博客主页： 【小扳_-ZEEKLOG博客】 ❤感谢大家点赞👍收藏⭐评论✍ 文章目录         AI系统具有许多优势         1.0 项目介绍         1.1 项目功能         1.2 用户端功能         2.0 用户登录         3.0 首页界面         4.0 物件管理功能         5.0 用户管理功能         6.0 区域管理功能         7.0 物件日志管理功能         8.0 操作日志         AI系统具有许多优势         1）自动化：AI 系统能够自动化执行任务，减少人力和时间成本。它们可以自动处理大量数据并执行复杂的计算，从而提高效率。         2）智能决策：AI 系统可以通过学习和分析数据来做出智能决策。

By Ne0inhk