能否举例说明贪心算法和动态规划的应用场景？

贪心算法通常用于解决那些可以分解成若干个局部最优解的问题，它在每个阶段选择当前看起来最好的解决方案，期望最终能得到全局最优。例如：
1. **最值路径问题**：如霍夫曼编码、Dijkstra算法寻找两点之间的最短路径，每次选择距离最近的节点加入到已选路径中。
2. **背包问题**：0-1背包问题中，贪心地选取单个物品价值最高的放入背包，直到无法再装。

动态规划则适合于具有重叠子问题和最优子结构的问题，通过保存中间结果避免重复计算。比如：
1. **斐波那契数列**：计算第n项时，先求前两项，而不是每次都从头开始算，避免了重复工作。
2. **最长公共子序列**：给定两个序列，找出它们的最长共同部分，通过构建一个二维数组存储子问题的最优解。