算法萌新如何学好动态规划（3）本文是「动态规划」系列文章

文章插图
本文是「动态规划」系列文章的第三篇，作为算法萌新如何学好动态规划（2）的一个延伸。本篇文章将主要聚焦于动态规划经典模型 —— 背包问题的讲解。
背包问题属于线性 DP 模型，之所以单独拎出来讲，主要是因为该问题信息量大且十分重要，属于面试中常考且必会的知识，因此我们将其放在本系列的第三篇进行介绍。
本文一共分为三个部分，具体内容框架如下所示：
文章插图
文章插图
前文回顾解题思路回顾回顾动态规划系列的第一篇文章，动态规划解题过程一共分为两步，一是确定「DP 状态」，二是确定「DP 转移方程」。
「DP 状态」的确定有两大原则，一是「最优子结构」，二是「无后效性」，简要概括就是将原问题划分为多个子问题，且「大规模子问题最优值」仅与「小规模子问题最优值」有关，与「小规模子问题最优值」是如何得到的无关。
此处的「大规模」与「小规模」，就是「DP 问题」的关键所在，也是 DP 问题分类的重要标准。
确定完「DP 状态」后，只需要分类讨论、细心枚举各种情况，即可得到「DP 转移方程」。
大家在看本文时，一定要细心体会每一个经典背包模型的「DP 状态」与「DP 转移方程」，认真思考每一个模型中这两部分是如何得到的。学习不同经典模型，理解模型本质，才能不断加深对「动态规划」问题的理解。
线性 DP 特点回顾线性划分 DP 规模的动态规划算法被统称为线性 DP 。在线性 DP 中， DP 状态从「小规模」转移到「大规模」的同时， DP 状态沿着各个维度线性增长。
我们在动态规划系列的第二篇文章中介绍了三个常见的线性 DP 模型，分别是「最长上升子序列 LIS」、「最长公共子序列 LCS」以及「数字三角形」，其特点如下图所示。
文章插图
本文将介绍第四个线性 DP 模型，即「背包问题」。由于背包问题也是线性 DP 问题，因此也符合线性 DP 的特点，即 DP 状态沿着各个维度线性增长，大家可以在下文中着重关注一下这一特点。
文章插图
背包问题概述常见的背包问题一共有三类，分别是「0/1 背包」、「完全背包」以及「多重背包」，接下来我们将依次进行介绍。
0/1 背包0/1 背包的基本模型如下所示：
一共有 N 个物品，其中第 i 个物品的体积为
文章插图
，价值为
文章插图
。现要求选择一些物品放入一个容积为 M 的背包中，使得物品总体积不超过 M 的前提下，物品总价值最大。
现在我们来思考下如何根据线性 DP 的知识来解决这个问题。
线性 DP 的特点是 DP 状态沿着各个维度线性增长。而本问题中只有三个参数，分别是物品编号、物品体积以及物品价值。由于我们要求的是物品总价值最大，因此不难想到令 DP 状态为
文章插图
，表示仅考虑前 i 个物品，所选物品总体积为 j 时的最大物品总价值。
确定「DP 状态」后，我们来考虑「DP 转移方程」是什么。
对于第 i 个物品来说，它只有两种状态，即要么取，要么不取。如果不取第 i 个物品，则
文章插图
；如果取第 i 个物品，则
文章插图
，因此我们得到如下「DP 转移方程」：
文章插图
其中初值
文章插图
为负无穷，其中
文章插图
，最终答案为
文章插图