动态规划综述

作者:江月迟迟

发表于:2024-12-10

字数统计:522 字

预计阅读2分钟

动态规划使用有限个状态(?)，每一个状态都从上一个状态推导出来，是一种记录状态的解决方案。区别于贪心，贪心通过拆分大问题成为子问题，找到无状态的若干子问题，然后叠加，即是从局部最优推出全局最优。动态规划则需要找到重叠子问题，找到状态的转移。

步骤

1. 明确dp数组的含义（一维？二维？甚至三维？每个维度的大小选择什么）以及下标的含义（下标从0开始，一直到i，和j的元素的的所求子问题，第i天的第几个状态（表示什么））
2. 确立状态，通过逻辑分析确定状态转移方程
3. 通过状态转移方程，明确第一个状态从哪开始，完成第一个状态的初始化
4. 确定遍历顺序
   1. 01背包
      1. 二维数组对物品和背包遍历顺序无要求
      2. 滚动数组，只能先遍历物品（外层）再遍历背包容量（内层），第二层循环从大到小以免覆盖
   2. 完全背包
      1. 纯完全背包对顺序无要求
      2. 求组合数：外层遍历物品，内层遍历背包
      3. 求排列数，外层遍历背包，内层遍历物品（可以理解为，在背包大小不同时，物品总会充分塞满背包，所以会找到更多的情况）
      4. 解释：
         1. 比如物品{1，5}，先遍历物品，会得到若干个背包里装1的情况，再循环，会得到若干个背包里装了1之后，选择是否装5的情况，所以装了{1,?5}
         2. 比如物品{1, 5}，先遍历背包，再遍历物品，会得到若干个物品装进背包里的情况，如果一个{1,5}是最优解，那么会得到这个背包里装1后选择5，和装5后选择1的情况，即是{1,5}和{5, 1}
5. 举例推导dp数组