一直进步 做喜欢的

动态规划（Dynamic Programming）算法是一种将大问题分解为子问题的优化算法，其基本思想是将问题分解为子问题，分别求解子问题的最优解，最后将子问题的最优解组合成原问题的最优解。知识点：

• 三要素：重叠子问题、最优子结构、状态转移方程
• 实现：动态规划算法通常采用自底向上或自顶向下的方式进行求解。自底向上的方法需要先求解小规模的子问题，再根据子问题的解求解大规模的子问题，直至求解原问题。自顶向下的方法则是从原问题开始，逐步将问题分解为子问题，并通过记忆化搜索的方式将已经求解过的子问题记录下来，避免重复计算。即带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
• 应用：动态规划算法常用于求解具有重叠子问题和最优子结构的问题。如在路径规划、背包问题、编辑距离等领域。其中最经典的应用是背包问题，通过动态规划算法可以高效地求解背包问题的最优解。
• 优化：动态规划算法的时间复杂度往往较高。常用的优化方法包括状态压缩、空间优化、滚动数组等。状态压缩可以将问题的状态表示压缩成一个整数或者一个二进制数，从而减少状态的存储空间。空间优化可以通过仅保存部分状态，避免保存所有状态，从而减少空间使用。滚动数组则是通过循环利用数组来减少空间使用。另外，在实际应用中可以根据问题的特点进行算法的优化，例如在路径规划中，可以使用A算法等算法加速求解过程。
  -*类型题：都具有递推性质
  1. 求最优解，典型问题是背包问题，当前问题的最优解取决于子问题的最优解（最优子结构）。
  2. 计数类，如统计方案数的问题，当前问题的方案数取决于子问题的方案数。

遇到求最值的问题，基本都是由动态规划算法来解决

• 解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的最后，然后一步步往前移动，缩小问题的规模
• 像子数组、子序列这类问题，你就可以尝试定义 dp[i] 是以 nums[i] 为结尾的最大子数组和/最长递增子序列，因为这样定义更容易将 dp[i+1] 和 dp[i] 建立起联系，利用数学归纳法写出状态转移方程
  1. 涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]。
  2. 只涉及一个字符串/数组时（比如本文要讲的最长回文子序列），dp 数组的含义如下：在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]。

解题步骤：

1. 确定 base case
2. 确定「状态」，也就是原问题和子问题中会变化的变量
3. 确定「选择」，也就是导致「状态」产生变化的行为
4. 明确 dp 函数/数组的定义。根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组
5. 动态规划问题的最后一步优化，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试缩小 DP table 的大小，只记录必要的数据，从而降低空间复杂度。

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)