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.结果

         即所有路段的最大值的最大值。

        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 条路段。