动态规划（Dynamic Programming, DP）#

空间换时间。动规VS分治：动规和分治都是分解为子问题，但动规是纵向的，代代相传，分治是横向的，兄弟分家。

什么时候不适合使用动态规划#

动态规划（Dynamic Programming, DP）在解决某些问题时非常高效，但并不是所有问题都适合用动态规划。以下几种情况中，动态规划通Answer：

问题没有最优子结构性质（Optimal substructur）
- 动态规划的前提是问题具有最优子结构，即子问题的最优解能构成原问题的最优解。
- 如果子问题的最优解不能组合成原问题的最优解，则动态规划无效。例如，寻找路径中有“全局约束”或路径顺序要求的问题可能不具备最优子结构。
问题没有重叠子问题（Overlapping sub-problems）
- 动态规划的另一前提是存在重叠子问题，即同一个子问题会被多次计算。
- 如果问题的每个子问题都是独立且只被计算一次，动态规划的优势就消失了。在这种情况下，通常使用分治法更合适。
状态和状态转移方程难以定义
- 如果问题很难划分为明确的状态和状态转移方程，设计动态规划的解法会变得非常复杂。
- 有些问题的状态空间过于庞大或转移条件不规则，导致无法找到合适的转移方程，这时也不适合用动态规划。
需要获得所有解，而不仅仅是最优解
- 动态规划主要用于寻找问题的最优解或计数解的数目，而不是用于获取所有可能的解。
- 对于要求枚举所有解的组合问题，通常回溯法或递归更合适。
问题是非确定性或不满足最优解递推条件
- 动态规划依赖于确定性的递推过程，而在概率性、非确定性问题中，不同路径的概率差异或条件差异可能导致DP的逻辑失效。
- 此类问题往往用其他方法（如随机算法、启发式算法）更为适合。

贪心#

什么时候能用贪心得到最优解？#

贪心算法能够得到最优解的情况，满足以下条件：

贪心选择性质（Greedy Choice Property）

每一步的局部最优选择可以逐步构建出问题的全局最优解，即当前所作的贪心选择不会影响最终解的最优性。
例如，在活动选择问题中，选择结束时间最早的活动是局部最优的选择，且不会影响其他活动的安排，因此可以达到全局最优解。

最优子结构性质（Optimal Substructure Property）

问题的最优解包含了其子问题的最优解。也就是说，问题可以被分解成更小的子问题，通过解决子问题的最优解可以构建出整个问题的最优解。
例如，在最短路径问题中，求从起点到终点的最短路径可以通过分解成更小的最短路径来逐步构建，因此使用贪心算法（如 Dijkstra 算法）可以得到最优解。

贪心算法的适用场景举例

活动选择问题：选择相互兼容的最大活动集合，选择结束时间最早的活动可以保证最优解。
最小生成树问题：在带权无向图中找到总权值最小的生成树，Prim 算法和 Kruskal 算法都使用了贪心策略。
单源最短路径问题（非负权值）：Dijkstra 算法对无负权图的单源最短路径问题使用贪心策略，选择当前最近的未访问顶点，能保证得到最优解。
硬币找零问题（特定面额集合）：当硬币的面额满足特殊结构（如美国常用面额1分、5分、10分和25分），贪心策略可以得到最少数量的硬币组合。对于像这样的面额序列，贪心算法也能得到最优解。

贪心算法可能失败的情况

背包问题：01背包问题不能使用贪心算法来获得最优解，因为选择最有价值或单位重量价值最高的物品可能导致最终的总价值不是最大。
硬币找零问题（任意面额）：当面额没有特定结构时（如3分和4分等），贪心算法并不总能生成最优解。