【知识总结】动态规划合集

博主： Fivk
发布时间：2022 年 01 月 04 日
1087 次浏览
1599字数
分类：知识总结

## 闫氏dp分析法

用于求有限集中的最值。方法：依次考虑，层层递进，将每一个条件从1开始考虑，再将每一种情况用数组的方式保存结果。那么当条件增加到2的时候就可以通过在条件为1的时候所保存的数据作为参考，得到条件为2时的最佳结果。

![](https://blog.fivk.cn/usr/uploads/2022/01/3081956191.png)

闰式DP分析法：`https://www.bilibili.com/video/BV1X741127ZM?share_source=copy_web`

背包九讲：`https://www.bilibili.com/video/BV1qt411Z7nE?share_source=copy_web`

# 一.背包问题

#### 01背包问题：每件物品最多只能用一次

第`i`个物品选还是不选
</div>

<div class="inner-content" >
<p class="inser-title">【动态规划】01背包</p>
<div class="inster-summary text-muted">
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪...
</div>
</div>
</a>

</div>

</div>

#### 完全背包问题：每件物品有无限个

第`i`个物品选几个（可选0个）
</div>

<div class="inner-content" >
<p class="inser-title">【动态规划】完全背包</p>
<div class="inster-summary text-muted">
基本思考框架废话少说，看看什么是完全背包：完全背包有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。...
</div>
</div>
</a>

</div>

</div>

#### 多重背包问题（优化）：每件物品个数可能不同

第`i`个物品选还是不选（数量限制）
</div>

<div class="inner-content" >
<p class="inser-title">【动态规划】多重背包</p>
<div class="inster-summary text-muted">
前言多重背包暴力算法其实和完全背包暴力算法差不多，但优化方面相对复杂了很多，多重背包不能像完全背包一样推导出状态转...
</div>
</div>
</a>

</div>

</div>

#### 分组背包问题：物品有`N`组，每个物品有若干个

第`i`**组**物品选哪个
</div>

<div class="inner-content" >
<p class="inser-title">【动态规划】分组背包</p>
<div class="inster-summary text-muted">
理解分组背包：N组：水果、蔬菜水果：葡萄、香蕉、苹果蔬菜：萝卜、白菜分组背包问题有 N 组物品和一个容量是 V 的...
</div>
</div>
</a>

</div>

</div>

# 二.线性DP

线性dp往往指在一个序列上进行的dp，当然也可能有两个甚至多个序列。

</div>一般来讲，线性dp的三个步骤分别有以下特点：

设计状态：至少有一维表示当前考虑的对象在数列上的位置。

状态转移：必须找到这条线上前面的位置的dp值来推出当前位置的dp值。

边界条件：第一个位置单独讨论。

#### 数字三角形（入门必备）

<div class="inner-content" >
<p class="inser-title">【动态规划】数字三角形</p>
<div class="inster-summary text-muted">
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到...
</div>
</div>
</a>

</div>

</div>

#### 最长上升子序列

<div class="inner-content" >
<p class="inser-title">【动态规划】最长上升子序列</p>
<div class="inster-summary text-muted">
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数 N。第二行包含 N...
</div>
</div>
</a>

</div>

</div>

#### 最长公共子序列

<div class="inner-content" >
<p class="inser-title">【动态规划】最长公共子序列</p>
<div class="inster-summary text-muted">
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少...
</div>
</div>
</a>

</div>

</div>

# 三.区间DP

## 概念

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状态  表示将下标位置  到  的所有元素合并能获得的价值的最大值，那么 ， 为将这两组元素合并起来的代价。

区间 DP 的特点：

**合并** ：即将两个或多个部分进行整合，当然也可以反过来；

**特征** ：能将问题分解为能两两合并的形式；

**求解** ：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

## 例题

#### 石子合并

<div class="inner-content" >
<p class="inser-title">【动态规划】石子合并</p>
<div class="inster-summary text-muted">
设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N...
</div>
</div>
</a>

</div>

</div>

# 四.计数类DP

#### 整数划分

<div class="inner-content" >
<p class="inser-title">【动态规划】整数划分</p>
<div class="inster-summary text-muted">
一个正整数 n 可以表示成若干个正整数之和，形如：$n=n_1+n_2+…+n_k$，其中 $n_1≥n_2≥…≥...
</div>
</div>
</a>

</div>

</div>

# 五.计数位统计DP

<div class="inner-content" >
<p class="inser-title">【动态规划】计数问题</p>
<div class="inster-summary text-muted">
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。例如，a=1024，b=1032，...
</div>
</div>
</a>

</div>

</div>

# 六.状态压缩DP

<div class="inner-content" >
<p class="inser-title">【动态规划】蒙德里安的梦想</p>
<div class="inster-summary text-muted">
求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。例如当 N=2，M=4 时，共有 5 种方案。...
</div>
</div>
</a>

</div>

</div>

最后修改：2022 年 01 月 25 日

如果觉得我的文章对你有用，请随意赞赏

【知识总结】动态规划合集

Fivk • 2022 年 01 月 04 日

## 闫氏dp分析法

![](https://blog.fivk.cn/usr/uploads/2022/01/3081956191.png)

闰式DP分析法：`https://www.bilibili.com/video/BV1X741127ZM?share_source=copy_web`

背包九讲：`https://www.bilibili.com/video/BV1qt411Z7nE?share_source=copy_web`

# 一.背包问题

#### 01背包问题：每件物品最多只能用一次

第`i`个物品选还是不选
</div>

#### 完全背包问题：每件物品有无限个

第`i`个物品选几个（可选0个）
</div>

#### 多重背包问题（优化）：每件物品个数可能不同

第`i`个物品选还是不选（数量限制）
</div>

#### 分组背包问题：物品有`N`组，每个物品有若干个

第`i`**组**物品选哪个
</div>

# 二.线性DP

线性dp往往指在一个序列上进行的dp，当然也可能有两个甚至多个序列。

</div>一般来讲，线性dp的三个步骤分别有以下特点：

设计状态：至少有一维表示当前考虑的对象在数列上的位置。

状态转移：必须找到这条线上前面的位置的dp值来推出当前位置的dp值。

边界条件：第一个位置单独讨论。

#### 数字三角形（入门必备）

#### 最长上升子序列

#### 最长公共子序列

# 三.区间DP

## 概念

区间 DP 的特点：

**合并** ：即将两个或多个部分进行整合，当然也可以反过来；

**特征** ：能将问题分解为能两两合并的形式；

**求解** ：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

## 例题

#### 石子合并

# 四.计数类DP

#### 整数划分

# 五.计数位统计DP

# 六.状态压缩DP

【知识总结】动态规划合集

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【项目实战】小兔鲜儿Vue3企业级项目

【C】指针与const：指针本身和所指的变量都可能是const

【数据结构】PTA 公路村村通（最小生成树Prim算法引入）

【C】结构体指针成员深拷贝问题

【算法基础】二维差分

【知识总结】动态规划合集