[导读]：超平老师的Scratch蓝桥杯真题解读系列在推出之后，受到了广大老师和家长的好评，非常感谢各位的认可和厚爱。作为回馈，超平老师计划推出《Python蓝桥杯真题解析100讲》，这是解读系列的第89讲。
先来看看题目的要求吧。
时间限制：3000MS
内存限制：589824K8
编程实现：
小马需要将N件物品从河的一岸搬运到河的另一岸，每次搬运的物品为1到3件。请问小马将N件物品全部搬运过去有多少种方案。
例如：N = 3，将3件物品全部搬运过去有4种方案：
方案一：第一次搬运1件，第二次搬运1件，第三次搬运1件；
方案二：第一次搬运1件，第二次搬运2件；
方案三：第一次搬运2件，第二次搬运1件；
方案四：一次搬运3件。
输入描述：
输入一个正整数N，表示需要搬运的物品数
输出描述：
输出将N件物品全部搬运过去有多少种方案
样例输入:
3
样例输出：
4
评分标准：
10分：能正确输出一组数据；
10分：能正确输出两组数据；
20分：能正确输出三组数据；
20分：能正确输出四组数据。
这是一道经典的算法题，涉及的知识点包括循环、条件、列表、递归、动态规划等。
f(n) = f(n - 1) + f(n - 2)f(n) = f(n - 1) + f(n - 2) + f(n - 3)搬运3件物品，那么搬运n - 3件物品的方案数为f(n - 3)； 搬运2件物品，那么搬运n - 2件物品的方案数为f(n - 2)； 搬运1件物品，那么搬运n - 1件物品的方案数为f(n - 1)；
递归算法 动态规划 递推算法
思路有了，接下来，我们就进入具体的编程实现环节。
递归算法
动态规划
递推算法
1. 递归算法
递归算法的重点是定义递归函数，代码如下：
代码比较简单，但是随着n的增加，代码运行的时间会越来越长，效率会急剧下降。
其原因在于存在大量重复的计算，可以增加一个备忘录将每一次的计算结果保存起来，避免重复计算。
使用带备忘录的递归代码如下：
代码不多，强调一点，这里的memo列表就是备忘录，前3项不需要保存，从第4项开始保存，对应于memo[4]。
有了备忘录，算法效率大大提高。
2. 动态规划
这里的推导公式（状态转移方程）和初始状态都已经确定好了，代码就比较简单了，如下：
代码并不多，说明4点：
1). 这里定义函数f(n)用于计算搬运n件物品的方案数量，主要是为了方便处理边界条件，但它不是递归函数；
2). Python支持多变量赋值运算，因此可以直接写成dp[1], dp[2], dp[3] = 1, 2, 4，代码看起来更加紧凑；
3). 在循环计算的时候，从第4项开始，所以range()函数的起点是4；
4). dp列表的最后一项就是要计算的方案数量，可以使用dp[n]获取，也可以使用dp[-1]获取。
3. 递推算法
针对上面的动态规划算法，仔细想一想，每一项只和前3项有关，是不是只要保存这3项就可以了呢？
答案是肯定的，只需要4个变量就够了，1个表示当前项，另外3个用来保存前3项，从而节省了一个列表，这就是递推的写法，也叫迭代，代码如下：
代码不难，强调一点，由于每一次都需要保存最后3项，需要不断更新f1，f2，f3的值，这就是f1, f2, f3 = f2, f3, f4的作用。
循环语句；
条件语句；
列表；
递归算法；
动态规划函数；
递推算法；
本题分值为60分，难度中等。关键点有两个，一是找到搬运物品方案的规律，确定好推导公式，二是使用多种算法来实现。
在找规律确定推到公式的问题时，一定要学会运用递归思维，将问题简化为两个步骤。最后一步保留，最后一步之前的所有步骤当作一步，然后看最后一步是如何计算出来的。切不可小瞧了这一点，在编程中，有很多问题都可以使用这一思维来解决。
本教程讲解了3种解决方案，这3种方案绝不是孤立的，它们之间都有一个共同的观点，这就是推导公式。
实际上，凡是有推导公式的问题，基本上可以采用这3种算法，尤其是带备忘录的递归和动态规划。如果说递归是自顶向下的推导过程，那么动态规划就是自底向上的推导过程。
和斐波那契数列相关的题目在历届真题中多次出现，如下：
你可以放在一起来分析对比，以加深理解。
你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。
需要源码的，可以添加本人微信。
另外，超平老师创建了一个蓝桥杯备考交流群，这是专门为老师和家长打造的免费社群，您可以与来自全国各地的老师、家长共同交流经验，分享学习心得。
超平老师也会给大家带来及时的赛事动态，备考攻略，真题资源分享，帮助各位更好地备考第15届蓝桥杯赛事，力争取得优异的成绩。
扫码或长按加入微信群
