蓝桥杯动态规划基础篇（一）

一、什么是动态规划？有套路吗？

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

用简单通俗的话来说：对于一个原问题，我们把这一个原问题拆分成多个子问题，直到子问题可以直接解决，再把子问题答案保存起来，以减少重复计算，使用子问题答案反推，得出原问题解。

动态规划的实现步骤：

1. 确定是否为动态规划问题：是否可以把这个问题分解成可以求解的子问题
2. 找关系：分解后的子问题之间有什么联系？确定原问题的子问题数量也很重要
3. 表达递归关系：不要着急写代码，在写代码之前清楚地表达递归关系可以加强你对问题的理解并使过程高效
4. 决定解决问题的迭代或递归方法：递归更好
5. 添加记忆：记忆是存储子问题的结果并在需要解决类似的子问题时再次调用它们的过程。这将降低问题的时间复杂度。如果我们不使用记忆，类似的子问题会重复解决，这可能导致指数时间复杂度。
6. 实现

二、动态规划的特征

重要的是要知道何时应用动态规划算法，让我们了解动态问题的 2 个特征

1. 最优子结构：如果一个问题的最优解包含子问题的最优解，则该问题是最优子结构。只有满足最优子结构，才能用动态规划的方法求解。如果问题具有最优子结构，我们可以递归求最优解。此外，如果问题没有最佳解决方案，则没有定义递归算法的基础，也是不能使用动态规划方法求解。
2. 重叠子问题：如果递归算法重复访问相同的子问题，则该问题称为重叠子问题。如果任何问题都有重叠的子问题（公共子子问题），那么我们可以通过只计算一次来改进子问题的重复实现。如果问题没有重叠的子问题，那么使用动态规划算法来解决问题是不可行的。 画个图说明：

三、动态规划三元素

正如上面所了解的，动态规划是将问题划分为各种子问题以找出最佳解决方案的算法。在使用动态规划方法解决问题陈述时，将问题总共分为3个元素以获得最终结果。这些元素是：

1. 子结构： 子结构是将给定的问题陈述划分为更小的子问题的过程。在这里，我们设法根据子问题的解决方案来确定原始问题的解决方案。
2. 表结构：子问题的解决方案需要解决后存储到一个表中。这很重要，因为我们知道，动态编程会多次重用子问题的解决方案，这样我们就不必一次又一次地重复解决同一个问题。
3. 自下而上的方法：使用表格组合子问题的解决方案以达到最终结果的过程。该过程从解决最小的子问题开始，然后将它们的解决方案与不断增加的子问题结合起来，直到获得原始问题的最终解决方案。

四、生活中的动态规划

想象一下，你想去几条街外的一家新杂货店，但你不知道怎么去那里，这是你就有多条测试的路线，要解决通往商店的路线的子问题，您可以在智能手机的地图上查找路线，然后前往那里。如果您以递归方式思考，那么每次您想去商店时，你都必须花时间再次查找路线。取而代之的是，我们自然而然地动态思考，从我们第一次查找商店时就记住了去往商店的方向，因此我们以后去的时候就不需要花时间去查找它们了。

五、斐波那契数列 5.1 问题

斐波那契数基本规律：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

斐波那契数列 Fn 由递归关系定义：

F n = F n-1 + F n-2

在python中递归基本方法：

def r_fibo(n): 
   if n