2026.3.29

一、背包问题

动态规划理解方式

dp问题没有模板，重在多刷题，积攒解题经验。

但我们可以用以下思维方式来理解dp问题，帮助我们更好地学习动态规划。

dp可分为状态表示和状态计算两部分。

状态表示

其中，状态表示分为集合和属性两个小部分。对于背包问题来说，集合一般指的是所有选法，且集合需要满足2个条件：1. 从前i个物品中选 2.总体积≤j

也就是说，我们可以用一个二维集合f[i，j]，表示所有从前i个物品中选择，且总体积≤j的所有选法，这就是这个问题的状态表示中的集合部分，是一个抽象的概念。

接下来是状态表示的属性部分。这个非常容易理解，我们最终要求一个值，所以f[i，j]集合储存的是集合中的某个属性，可能是最大值（MAX），最小值（MIN），也可能是数量，但总之是这个抽象集合中的一个具体值。对于背包问题而言，通常是最大值。

状态计算

我们求解一个问题，肯定是要得到最终结果的，状态计算的作用就是这个。

那么该如何计算，从而求得一个问题结果？

我们用了集合划分的方法，这是状态计算的核心。

但不同问题的划分方法不一样，这就是为什么dp问题没有一个统一的模板，只能总结出一个大致的理解方式。

那么我们接下来以01背包为例，先讲一下01背包的集合划分是什么样的。

01背包

01背包的状态表示部分，已经在上面作为例子讲述过，不再复述。我们直接来看状态计算：

假设我们要求f[i，j]——从前i个物品中选，且体积≤j的所有选法中，价值最大的选法。