动态规划【自用】
动态规划是数学和计算机科学中使用的一种方法，通过将复杂问题分解为更简单的子问题来解决这些问题。通过仅求解每个子问题一次并存储结果，它避免了冗余计算，从而为各种问题提供了更高效的解决方案。
关键概念：
- 最优子结构：问题的最优解可以从其子问题的最优解中构建。
- 重叠的子问题：子问题通常在较大的问题中重复出现，从而导致冗余计算。
- Memoization / Tabulation：存储子问题的解决方案以避免重新计算。
在继续之前，您必须解决的动态规划算法的一些重要和最常见的问题是：
| 问题 | 描述 |
|---|---|
| 斐波那契数列 | 使用动态规划生成斐波那契数列，以避免重复计算。 |
| 最长公共 Subsequence | 求两个序列共有的最长子序列。 |
| 最长递增的子序列 | 查找给定序列的最长子序列，其中元素按升序排序。 |
| 0/1 背包问题 | 确定通过选择具有给定权重和值的项目（不超过指定的重量限制）可以获得的最大值。 |
| 杆切割问题 | 通过将给定长度的棒切割成小块并根据给定的价格出售来最大化利润。 |
| 硬币兑换问题 | 确定使用一组给定面额的硬币对给定数量进行兑换的方法数量。 |
| 编辑距离 | 查找将一个字符串转换为另一个字符串所需的最小操作数 （插入、删除、替换）。 |
| 子集和问题 | 确定是否存在具有给定总和的给定集的子集。 |
| 最长回文子序列 | 找到给定序列的最长子序列，即回文。 |
| 最大子数组总和 | 在给定的一维数组中查找具有最大和的连续子数组。 |
| 分区等于子集和 | 确定是否可以将给定集划分为两个总和相等的子集。 |
| 最低成本路径 | 查找从给定网格的左上角到右下角的最低成本路径。 |
| 最大 Product Subarray | 查找给定一维数组中具有最大乘积的连续子数组。 |
相关文章：
| 经典问题 | 动态规划 | Link |
|---|---|---|
| 0-1 背包问题 | ✅ | 0-1 背包问题【图文】 |
| 部分背包问题 | ❌ | |
| 旅行售货员问题 | ❌ | |
| 最长公共子序列 | ✅ | 最长公共 Subsequence【图文】LCS【动画】LCS_2【动画】 |
| 最小生成树 | ❌ | |
| 单源最短路径 | ❌ | |
| 八皇后问题 | ❌ | |
| 装载问题 | ❌ | |
| 批处理作业调度 | ❌ | |
| 最大团问题 | ❌ | |
| 装箱问题 | ❌ |