动态规划与贪心，动态规划核心思想

贪心：

概述：

决策者当前的做出决策不会影响到后续的决策选择，那么每一步都做出最优的决策则可达到全局最优解。

以下我们来看一个

例子：

决策者要从状态A到达状态G，状态A经过决策b可以到达状态B，经过决策c可以到达状态C，以此类推，具体情况见下图。（边代表决策，节点代表状态）

观察此图可以发现一个很重要的点：状态B/C都可以到达状态E/F，即不管你选择决策b到达状态B，还是决策c到达状态C，都可以从状态B/C做出同等的代价e/f到达状态E/F，即当前的决策不会影响到后续的决策。

那么决策者可以在每一步的决策中都选择最优的方式到达下一个状态，以此达到全局最优的情况。

没明白？没事，和以下的动态规划对比一下就明白了。

动态规划：

动态规划的两个核心思想：

1.状态转移
2.记录状态（因为问题的特性：状态可能被多次调用，这个特性也是决定一个问题能否使用动态规划的关键点）

概述：

决策者当前的做出决策会影响到后续的决策选择，决策时，当前状态是从（前一状态的花费+转移花费）中选择一个最优的，从而达到一个状态转移到另一个状态的目的，最终使得达到目标状态时是最优的状态。

是不是听着和贪心很像，但是确有不同，贪心是只考虑了一条路，而动态规划是考虑了全局。

例子：

题目同上，状态转移图如下。

观察转移图我们可以发现，当前决策会影响到以后的决策选择，如到达了状态B就无法到达状态H（无法通过选择决策够到达H)。那么若采用贪心的策略就可能无法达到全局最优解，如A->B->E花费100，A->C->H花费120，但是E->G花费50，H->G花费20，若选择了A->B->E这条路，最后花费就是150大于A->C->H->G的花费140。

状态转移的具体过程：

1. 因为状态B前只能由状态A转移过来，所以：状态B=状态A花费+决策b花费
2. 同理：状态C=状态A花费+决策c花费
3. 状态E，H也同理；
4. 但是F则不同，其可以由两个状态转移过来，那么就选择两个状态中比较优的
   即:状态F=min( 状态C花费+决策f2花费,状态B花费+决策f1花费).
5. 那么由于状态E/F/H都是能到达当前状态的最优决策，目标状态G只要从三个的花费加上决策g花费的和中选择最小，即可达到全局最优。
   即：状态G=min( 状态E花费+决策g1花费,状态F花费+决策g2花费，状态H花费+决策g3花费).

记录状态分析：

通过以上过程，我们可以知道，状态B/C被重复调用了（计算状态E/F时调用了状态B，计算状态F/H时调用了状态C），这里体现了动态规划的核心思想除了状态转移外的另一核心思想：记录状态，因为一个状态可能被多次调用，为了避免从头计算达到这个状态的最优选择（暴力搜索，穷举），于是记录下当前状态的最小花费。

这样一来就把一个x^(a+b+c+…)的计算次数降低为x^a+x^b+x^c…，其中x代表每次的决策次数（简单假设每次决策次数都一样），abc代表每个阶段的步骤数

总结：

以上过程就显示出了动态规程和贪心求法之间的区别了，贪心是一条路走到黑，而动态规划是每一步的状态都由前一状态加上决策花费转移而来，一定是全局最优解，且通过记录状态的方式算法提高效率。

其实广义上来看贪心策略其实是动态规划策略的一种特殊情况。

以上。（好久没发文章了