Loading... ## 闫氏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背包问题:每件物品最多只能用一次 <div class="tip inlineBlock success"> 第`i`个物品选还是不选 </div> <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1031.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/1671317345.png);background-size: cover;"></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> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> #### 完全背包问题:每件物品有无限个 <div class="tip inlineBlock success"> 第`i`个物品选几个(可选0个) </div> <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1039.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/2819061066.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">【动态规划】完全背包</p> <div class="inster-summary text-muted"> 基本思考框架废话少说,看看什么是完全背包:完全背包有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> #### 多重背包问题(优化):每件物品个数可能不同 <div class="tip inlineBlock success"> 第`i`个物品选还是不选(数量限制) </div> <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1043.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/2311715602.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">【动态规划】多重背包</p> <div class="inster-summary text-muted"> 前言多重背包暴力算法其实和完全背包暴力算法差不多,但优化方面相对复杂了很多,多重背包不能像完全背包一样推导出状态转... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> #### 分组背包问题:物品有`N`组,每个物品有若干个 <div class="tip inlineBlock success"> 第`i`**组**物品选哪个 </div> <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1046.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/2692750078.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">【动态规划】分组背包</p> <div class="inster-summary text-muted"> 理解分组背包:N组:水果、蔬菜水果:葡萄、香蕉、苹果蔬菜:萝卜、白菜分组背包问题有 N 组物品和一个容量是 V 的... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> # 二.线性DP <div class="tip inlineBlock success"> 线性dp往往指在一个序列上进行的dp,当然也可能有两个甚至多个序列。 </div>一般来讲,线性dp的三个步骤分别有以下特点: 设计状态:至少有一维表示当前考虑的对象在数列上的位置。 状态转移:必须找到这条线上前面的位置的dp值来推出当前位置的dp值。 边界条件:第一个位置单独讨论。 #### 数字三角形(入门必备) <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1048.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/2903410270.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">【动态规划】数字三角形</p> <div class="inster-summary text-muted"> 给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> #### 最长上升子序列 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1050.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/2406788584.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">【动态规划】最长上升子序列</p> <div class="inster-summary text-muted"> 给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数 N。第二行包含 N... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> #### 最长公共子序列 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1054.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/3377658528.png);background-size: cover;"></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> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> # 三.区间DP ## 概念 区间类动态规划是线性动态规划的扩展,它在分阶段地划分问题时,与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状态 表示将下标位置 到 的所有元素合并能获得的价值的最大值,那么 , 为将这两组元素合并起来的代价。 区间 DP 的特点: **合并** :即将两个或多个部分进行整合,当然也可以反过来; **特征** :能将问题分解为能两两合并的形式; **求解** :对整个问题设最优值,枚举合并点,将问题分解为左右两个部分,最后合并两个部分的最优值得到原问题的最优值。 ## 例题 #### 石子合并 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1057.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/2039114027.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">【动态规划】石子合并</p> <div class="inster-summary text-muted"> 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> # 四.计数类DP #### 整数划分 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1067.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/341918679.png);background-size: cover;"></div> <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> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> # 五.计数位统计DP <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1077.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/themes/handsome/assets/img/sj/4.jpg);background-size: cover;"></div> <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> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> # 六.状态压缩DP <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.fivk.cn/archives/1079.html" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.fivk.cn/usr/uploads/2022/01/2230381418.jpg);background-size: cover;"></div> <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> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> 最后修改:2022 年 01 月 25 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用,请随意赞赏