动态规划一

动态规划

概述

1. 动态规划通过将复杂问题分解为相互重叠的子问题，并利用存储中间结果来避免重复计算，从而高效解决具有最优子结构特性的问题
2. 其核心在于 “状态定义” 和 “状态转移”

实现步骤

1. 定义状态 (State Definition)
   1. 这是动态规划最基础且关键的一步。你需要定义一个或多个状态变量（通常用数组 dp来表示），并明确 dp[i]或 dp[i][j]所代表的具体含义
   2. 例如，在经典的斐波那契数列问题中，状态 dp[i]就表示第 i个斐波那契数的值
2. 确定状态转移方程 (State Transition Equation)
   1. 状态转移方程描述了较大问题的解如何由其较小子问题的解推导出来，是动态规划的灵魂
   2. 它建立了不同状态之间的关系
   3. 例如，在斐波那契数列中，状态转移方程就是 dp[i] = dp[i-1] + dp[i-2]
3. 初始化 (Initialization)
   1. 状态转移方程需要一个起点
   2. 你需要为最小的、不可再分的子问题（边界条件）设置初始值
   3. 例如，在斐波那契数列中，我们需要初始化 dp[0] = 0和 dp[1] = 1
4. 确定计算顺序 (Calculation Order)
   1. 确定是以自底向上（递推）还是自顶向下（记忆化搜索）的方式填充状态表
   2. 正确的计算顺序需要确保在计算一个状态时，它所依赖的子状态已经被计算过
5. 返回结果 (Return the Result)
   1. 根据状态定义，从填充好的 dp数组中返回最终问题的解
   2. 例如，计算第 n个斐波那契数，结果就是 dp[n]

实现方式

1. 概述

   1. 动态规划主要有两种实现方式，它们基于相同的原理，但思路和实现代码有所不同

2. 自底向上（递推）

   1. 从最小的子问题开始，逐步推导至原问题
   2. 效率高，无递归开销；通常空间优化更直接
   3. 可能需要计算所有子问题，即使有些并非必需

3. 自顶向下（记忆化搜索）

   1. 从原问题开始，递归分解为子问题，并记忆已解子问题
   2. 代码直观，更符合对问题的自然思考方式；只计算必要的子问题
   3. 递归存在函数调用开销，对于问题规模极大时可能栈溢出

背包问题

概述

1. 背包问题是一类经典的组合优化问题，在有限的背包容量下，如何选择物品才能使得总价值最大

01背包

1. 01背包问题是背包问题中最基础的形式，每种物品最多只能选择一次
2. 核心思路
   1. 使用动态规划，定义 dp[i][j]表示前i个物品在背包容量为j时能获得的最大价值
3. 状态转移方程
   1. 其中第一项表示不选第i个物品
   2. 第二项表示选择第i个物品

4. 状态转移方程解析1
   1. 从01背包问题的目标出发：在背包容量有限的前提下，从若干件只能选择一次（0或1） 的物品中挑选，使得总价值最大

4. 状态转移方程解析2
   1. 假设我们有3件物品和一个容量为5的背包
   2. 物品1：重量2，价值3
   3. 物品2：重量3，价值4
   4. 物品3：重量4，价值5

5. 理解
   1. 如果不选择第i个物品，那么j个容量的最大价值其实就是第i-1个物品的最大价值，也就是dp[i-1][j]，此时第i个物品的最大价值同样也是dp[i-1][j]
   2. 如果选择第i个物品，首先在容量j上面预留出weight[i]的重量大小，此时前i-1个物品的最大价值是在j-weight[i]容量的前提下的，也就是dp[i-1][j-weight[i]]，并由于选择了第i个物品，所以还要加上第i个物品的价值，最后就是dp[i-1][j-weight[i]]+value[i]
   3. 最后，在选择第i个物品和不选第i个物品时的价值的最大值里面，选大的，就是dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
6. 实现1

7. 实现2：使用一维数组，将空间复杂度从O(n×W)优化到O(W)
   1. 内层循环必须倒序遍历，防止物品被重复放入

完全背包

1. 概述
   1. 与01背包类似，但选择物品时每种物品可以多次选择
2. 状态转移方程
   1. 与01背包的区别在于第二项是dp[i][j - weight[i]]而不是dp[i-1][j - weight[i]]

3. 理解
   1. 如果不包含第i件物品，那么前i-1件物品在j容量的条件下的最大价值是dp[i-1][j]
   2. 如果包含第i件物品，预留出1个第i件物品的空间，容量条件变为j-weight[i],
      由于完全背包物品可以选择多次，所以可以在容量条件为j-weight[i]的情况下，直接使用有第i件物品的最大价值，就是dp[i][j-weight[i]]
      由于为i还预留了一个空间大小，所以还得加上value[i]，就是dp[i][j - weight[i]] + value[i]
      最后，还要在包含第i件物品和不包含第i件物品之间选最大值
4. 实现
   1. 内层循环为正序遍历，允许物品多次被选择

多重背包：二进制优化

1. 概述
   1. 多重背包问题中，每种物品有数量限制
   2. 就是说，在将物品装入背包时，每种物品最多只能装入一个预先设定的、有限的数量
2. 基本思路
   1. 可以将多重背包转化为01背包问题，但这种方法在物品数量较大时效率较低
3. 优化思路
   1. 二进制优化
   2. 本质上是一种将任意整数高效拆分为2的幂次组合的方法
4. 公式

5. 构造规律

   1. 寻找最大的基础幂次和
      首先，找到最大的整数 k，使得所有2的幂次之和 1+2+4+...+2*k*−1小于或等于 n
   2. 计算余项
      然后，用总数 n 减去这个已经能被幂次项覆盖的最大范围 (2^k−1)，剩下的数就是最后一项

6. 示例：假设一种物品有13件。朴素算法需要依次考虑拿0件、1件、2件...一直到13件，共14种情况

   1. 二进制优化后：
   2. 将13拆分为：1, 2, 4, 6（因为1+2+4=7, 13-7=6）
   3. 这样，我们得到了4个“新物品”，它们分别代表1件、2件、4件、6件原物品打包成的“物品包”
   4. 现在，问题转化为了一个01背包问题：对于这4个“物品包”，每个只能选一次

7. 二进制优化实现

多重背包：单调队列优化

其他

相互重叠的子问题

1. 概述
   1. 指的是在解决一个复杂问题的过程中，相同的、更小规模的子问题会被反复多次遇到和计算
   2. 就像是拆解一个大任务时，你会发现有些基础步骤是完全一样的，并且需要在不同阶段重复执行
      如果使用简单的递归方法，这些子问题就会被重复计算，导致效率急剧下降（例如斐波那契数列的递归解法会出现指数级的时间复杂度）
      动态规划通过“记忆化”（存储子问题的解）来避免这种重复劳动，每个子问题只计算一次，后续需要时直接查表即可

具有最优子结构特性的问题

1. 最优子结构
   1. 是指一个问题的最优解包含了其子问题的最优解
   2. 简单来说，你可以通过组合子问题的最优解来构造出整个问题的最优解
2. 意味着
   1. 一旦我们知道了所有子问题的最佳解决方案，我们就可以有效地构建出原问题的最佳解决方案
   2. 这种“由下而上”构建最优解的特性是最优子结构的核心

子问题重叠和最优子结构

1. 结论
   1. 一个问题只要是具有最优子结构的，那么可以使用动态规划算法来处理该问题
   2. 至于该问题是不是子问题重叠的，影响的仅仅是解决问题的效率