Drie🦋

第四章 动态规划 前面讲的分治法是将原问题分解为若干个规模较小、形式相同的子问题，然后求解这些子问题，合并子问题的解得到原问题的解。在分治法中，各个子问题是互不相交的，即相互独立。如果各个子问题有重叠，不是相互独立的，那么用分治法就重复求解了很多子问题，根本显现不了分治的优势，反而降低了算法效率。那该怎么办呢？ 动态规划闪亮登场了！ 4.1　神奇的兔子序列 公元1202年，意大利数学家列昂纳多•斐波那契（Leonardo Fibonacci）在《算盘全书》（Liber Abaci）中描述了一个神奇的兔子序列，这就是著名的斐波那契序列。 假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？如果是N对初生的兔子开始，M月后又会有多少对兔子呢？ 第1个月，兔子①没有繁殖能力，所以还是 1 对。 第2个月，兔子①进入成熟期，仍然是 1 对。 第3个月，兔子①生了1对小兔②，于是这个月共有2对（ 1+1=2 ）兔子。 第4个月，兔子①又生了1对小兔③。兔子②进入成熟期。 ...

第二章　贪心算法 从前，有一个很穷的人救了一条蛇的命，蛇为了报答他的救命之恩，于是就让这个人提出要求，满足他的愿望。这个人一开始只要求简单的衣食，蛇都满足了他的愿望，后来慢慢的贪欲生起，要求做官，蛇也满足了他。这个人直到做了宰相还不满足，还要求做皇帝。蛇此时终于明白了，人的贪心是永无止境的，于是一口就把这个人吞掉了。 所以，蛇吞掉的是宰相，而不是大象。故此，留下了“人心不足蛇吞相”的典故。 2.1　人之初，性本贪 我们小时候背诵《三字经》，“人之初，性本善，性相近，习相远。”其实我觉得很多时候“人之初，性本贪”。小孩子吃糖果，总是想要多多的；吃水果，想要最大的；买玩具，总是想要最好的，这些东西并不是大人教的，而是与生俱来的。对美好事物的趋优性，就像植物的趋光性，“良禽择木而栖，贤臣择主而事”“窈窕淑女，君子好逑”，我们似乎永远在追求美而优的东西。现实中的很多事情，正是因为趋优性使我们的生活一步一步走向美好。例如，我们竭尽所能买了一套房子，然后就想要添置一些新的家具，再就想着可能还需要一辆车子…… 凡事都有两面性，一把刀可以做出美味佳肴，也可以变成杀人凶器。在这里，我们只谈好的“贪心”。 ...