03-动态规划

type
status
date
slug
summary
tags
category
icon
password
 
动态规划（Dynamic Programming，简称 DP）是一种用于解决具有重叠子问题和最优子结构问题的算法设计思想。它通过保存子问题的中间结果，避免重复计算，从而大大提高效率。
 
特性
说明
重叠子问题
大问题可分解为多个相同的小问题
最优子结构
大问题的最优解由子问题的最优解构成
状态转移方程
当前状态依赖于之前的状态（核心）
记忆/表格法
使用数组保存子问题解，避免重复计算
 
  • 定义状态： 明确 dp[i] 的含义
  • 状态转移方程： 找出 dp[i] 和子问题 dp[j] 的关系
  • 初始化： 设定 dp[0], dp[1] 等边界值
  • 计算顺序： 通常是从小到大逐步推导
  • 返回值： 返回最终问题的解（如 dp[n]）
 

1️⃣ 斐波那契数列（自顶向下 vs 自底向上）

1.自顶向下(递归+记忆化搜索)

2.自底向上(动态规划迭代实现)

1.数组存储所有结果
 
2.仅保存前两项，优化空间

2️⃣ 最大子序和

给定一个整数数组 nums，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组[4,-1,2,1]的和最大，为6。
示例步骤分析（输入：[-2,1,-3,4,-1,2,1,-5,4]）
i
nums[i]
currSum（当前最大和）
maxSum（全局最大）
0
-2
-2
-2
1
1
max(1, -2+1) = 1
max(-2, 1) = 1
2
-3
max(-3, 1-3) = -2
max(1, -2) = 1
3
4
max(4, -2+4) = 4
max(1, 4) = 4
4
-1
max(-1, 4-1) = 3
max(4, 3) = 4
5
2
max(2, 3+2) = 5
max(4, 5) = 5
6
1
max(1, 5+1) = 6
max(5, 6) = 6
7
-5
max(-5, 6-5) = 1
max(6, 1) = 6
8
4
max(4, 1+4) = 5
max(6, 5) = 6

3️⃣ 背包问题（01 背包）

给定 n 个物品和一个容量为 W 的背包，每个物品有：
  • 重量 w[i]
  • 价值 v[i]
目标：
从中选择若干个物品放入背包，在不超过背包容量的前提下，使得总价值最大。

4️⃣ 编辑距离

 
上一篇
02-查找算法
下一篇
04-贪心算法
Loading...