动态规划和贪心算法的相同点和不同点

相同点：动态规划和贪心算法的都是一种递推算法，都是由局部最优解来推导全局最优解，具有最优子结构性质。

不同点：

• 贪心算法“自顶向下”遍历子问题，不保存所有子树情况；动态规划“自底向上”，保存所有子树情况
• 贪心算法并不从整体最优上加以考虑，它所做的选择只是在某种意义上的局部最优解，一般复杂度低；动态规划本质是穷举法，可以保证结果是最佳的，复杂度高。

贪心算法的几个案例

参考：https://blog.csdn.net/qq_32400847/art%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20etails/51336300

这里只记录下自己刚开始百思不得其解后来恍然大悟的问题

• 销售问题

7.销售比赛
在学校OJ上做的一道比较好的题，这里码一下。假设有偶数天，要求每天必须买一件物品或者卖一件物品，只能选择一种操作并且不能不选，开始手上没有这种物品。现在给你每天的物品价格表，要求计算最大收益。首先要明白，第一天必须买，最后一天必须卖，并且最后手上没有物品。那么除了第一天和最后一天之外我们每次取两天，小的买大的卖，并且把卖的价格放进一个最小堆。如果买的价格比堆顶还大，就交换。这样我们保证了卖的价格总是大于买的价格，一定能取得最大收益。

刚看到这个题，对标黑处的描述一直不理解，细看了作者的代码之后才明白自己的误区。

我的理解是这样的：为了保证最后手上没有物品，你买一件商品就必须卖一件。以两天为间隔，理想情况下，少的买多的卖，但是！并不限定你在这两天一定是一买一卖，当发现买的比以前任何一次卖的“更贵”，就拿这天和以前卖的“最贵”的那天交换，所以当前的这两天可能都是卖。我之前的误区在于：以为决定了一天“卖”或“买”之后，后面就不能改变了，但实际上这个尝试的过程，前面的步骤决定“卖”的，后面经过调整这天也有可能变成“买”。

POJ3253一道就是利用这一思想的典型例题。题目大意是有把一块无限长的木板锯成几块给定长度的小木板，每次锯都需要一定费用，费用就是当前锯的木板的长度。给定各个要求的小木板的长度以及小木板的个数，求最小的费用。以要求3块长度分别为5,8,5的木板为例：先从无限长的木板上锯下长度为21的木板，花费21；再从长度为21的木板上锯下长度为5的木板，花费5；再从长度为16的木板上锯下长度为8的木板，花费8；总花费=21+5+8=34。

这个题说的好像有点问题。后来我翻到了原题目：传送门http://poj.org/problem?id=3253

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.

题目大意是现有一整块长木板，问如何锯出几块给定长度的小木板，使得锯的费用最少？每次锯都需要一定费用，费用就是当前锯的木板的长度。例如：要求从长度为16的大木板分别锯出3,5,8长度的小木板各一块，价格最低为多少？

• 如果从长木板上先切3，再切一刀分为3和8，那么总费用=16+13=29
• 如果利用Huffman思想，先从长木板上先切8，再从8里切一刀成3,5，那么总费用=16+8=24