在备考算法的过程中，动态规划和贪心算法是非常重要的部分。对于这两种算法，首先要明确它们的适用条件。
一、适用条件
1. 动态规划
- 当问题具有最优子结构性质时，往往适合用动态规划。也就是说，问题的最优解可以由子问题的最优解构建而成。例如，在计算斐波那契数列时，F(n)=F(n - 1)+F(n - 2)，F(n)的最优解（值）依赖于F(n - 1)和F(n - 2)的最优解。
- 存在重叠子问题也是动态规划适用的场景。比如在计算从起点到终点的所有可能路径数量时，中间的某些节点会被多次用到。
2. 贪心算法
- 贪心算法适用于局部最优解能构成全局最优解的情况。例如，在找零钱问题中，如果货币面额是合理的（如1元、5元、10元等），每次都选择最大面额的货币来找零，这种局部的最优选择（拿最大面额）最终能得到全局的最优解（最少的货币张数）。
二、经典例题分析
1. 背包问题
- 动态规划解法：
- 设物品有n个，背包容量为C。定义dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。状态转移方程可能是dp[i][j]=max(dp[i - 1][j], dp[i - 1][j - w[i]]+v[i])，其中w[i]是第i个物品的重量，v[i]是价值。学习时，要多做不同规模数据的练习题，理解如何构建状态转移方程，以及边界条件（如i = 0或者j = 0时的情况）。
- 贪心算法解法：
- 如果按照单位重量价值（v[i]/w[i]）对物品进行排序，然后优先选择单位重量价值高的物品放入背包，在某些特殊情况下可以得到近似最优解。但要注意这种方法并不总是能得到精确的最优解。
2. 最短路径问题
- 动态规划：
- 例如Floyd算法，它通过逐步考虑更多的中间节点来更新两点之间的最短距离。设d[i][j][k]表示从i到j经过k个中间节点的最短距离，状态转移方程为d[i][j][k]=min(d[i][j][k - 1], d[i][k][k - 1]+d[k][j][k - 1])。学习时要理解这种多维数组状态表示的意义以及如何逐步优化计算过程。
- 贪心算法：
- Dijkstra算法就是贪心算法的应用。它每次选择未确定最短路径的节点中距离源点最近的节点，然后更新其相邻节点的距离。学习时要掌握如何构建优先队列来高效地选择最近的节点。
通过对这些经典例题的深入分析，对比动态规划和贪心算法的设计思路，能够更好地掌握这两种算法，在备考算法相关考试或者面试时更加游刃有余。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
