dp 是 c++ 之中一个简单而重要的算法，每一个 OIer 必备的基础算法，你知道它究竟是什么吗？
目录
一、简介
1.为什么不能贪心？
2.揭秘 dp
二、应用
1.定义
2.边界值
3.动态转移方程
4.结果
5.代码
一、简介
1.为什么不能贪心？
贪心简单而已理解，但为什么许多程序都不能贪心呢？因为贪心是求局部的最优解，非整体最优解！举个栗子：
你玩了一个吃豆游戏，这个游戏只能前进，不能后退，但有许多岔路，你随时都能看到整张地图。按照贪心，你会不管后面的路段（即从这个路口到下个路口的路），选择一个豆最多路段走。 但如果有一个路口有两条路，第一条路段上有一个豆，沿着他继续走，后面就是终点了。而第二条路段上，虽然一个豆也没有 但后面任何一条岔路都至少有两个豆：
注：从⭐️开始。
显然，选豆多的就错了！
2.揭秘 dp
dp 需要递推或递归（时间复杂度高，可用递推代替，不推荐）来实现，即若要算出算出 i 的最优解，就要算出 i-1 的最优解，若要算出i-1的最优解，就要算出 i-2 的 最优解······，最后需要一个边界值，即 0、1 或 2 的最优解，要不然递推就回输出 0，递归就回死循环。而从 i-1 到 i 的过程就是动态转移方程。
二、应用
刚才的吃豆游戏，搜索就可以得到 O(n) 的时间复杂度。但如果改变一下地图，有多条路段可以到达一条路，搜索的时间就明显不够了，我们可以尝试 dp：
1.定义
表示走过路段 i 的最大值。
2.边界值
即第一条路别无选择，只有一条路。
3.动态转移方程
，其中 j，j+1，j+2······ 表示所有可以到达它的路口的编号。
4.结果
即所有路段的最大值的最大值。文章来源：https://www.toymoban.com/news/detail-845588.html
5.代码
int f[1005] = {0};
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < mp[i].size();j ++){
f[i] = max(f[i],f[mp[i][j]] + v[i]);
}
}这里 mp 是存放地图的 vector ，mp[i][j] 表示与第 i 条路段相连的第 j 条路段。 文章来源地址https://www.toymoban.com/news/detail-845588.html
到了这里，关于c++ 算法之动态规划—— dp 详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
