跳房子游戏，本题是2021年10月24日举办的第13届蓝桥杯青少组Python编程选拔赛真题编程部分第5题。题目要求编程模拟跳房子游戏，计算出小明最少需要跳几次就可以完成游戏，完成游戏时哪只脚落地？
先来看看题目的要求吧。
编程实现：
小明和同学们玩跳房子的游戏，现给出一排房子，请计算出小明最少需要跳几次就可以完成游戏，完成游戏时哪只脚落地？（0代表左脚，1代表右脚）
游戏规则1：
地上画有n个正方形依次排开代表房子，每个房子里标有数字，数字代表最多可以跳几个房子，数字不能为0（如：数字为2，可以直接向前跳1个房子，也可以直接向前跳2个房子）。
例如：
地上画有5个正方形代表房子，房子里面的数字分别为2，1，4，2，1。
小明在第1个房子时可以选择跳到第2个房子或者第3个房子，为了所跳次数最少选择跳到第3个房子（房子数字为4）；房间数字为4，可以选择跳到第4个房子或者第5个房子，为了所跳次数最少选择跳到第5个房子。故至少需要跳两次就可以完成游戏。
游戏规则2：
只能单脚落地，左脚起跳右脚落地，右脚起跳左脚落地；第一次起跳为左脚。
例如：
小明一共跳两次，第一次左脚起跳，右脚落地；第二次右脚起跳，左脚落地；完成游戏时左脚落地。
输入描述：
第一行输入n个正整数，正整数之间用英文逗号隔开
输出描述：
输出两个整数，整数之间用英文逗号隔开；第一个整数表示最少跳的次数，第二个整数表示落地的脚（0代表左脚，1代表右脚）
样例输入：
2，1，4，2，1
样例输出：
这是一道算法题，涉及的知识点包括循环、列表、递归算法和动态规划等。
f(1)，如果可以跳跃f(2)，如果可以跳跃f(3)，如果可以跳跃...f(n - 1)，如果可以跳跃
思路有了，接下来，我们就进入具体的编程实现环节。
递归算法
动态规划
1. 递归算法
根据前面的思路分析，我们先定义递归函数，如下：
代码不多，说明3点：
1). 为了方便，这里用0表示第1个房间，1表示第2个房间，小明一开始就在第1个房间，不需要跳跃，所以返回0，要跳到第2个房间，一次就行，所以返回1；
2). 为了计算最小值，定义了遍历_min，同时将其设置为无穷大；
3). 对于任何一个房间i，都需要考虑从1 ~ i -1之间所有的房间，如果可以跨越，则计算其次数，然后获取最小次数。
接下来，获取输入的数据，调用函数处理即可，代码如下：
代码比较简单，说明两点：
1). 将输入的字符串，进行分解并转成整型，保存到rooms列表中，这里使用了列表推导式的编程技巧；
2). 计算最后落地脚是根据次数的奇偶性来判断的，如果是偶数，则为左脚，如果是奇数，则为右脚。
递归的代码比较好理解，但是有一个小问题，就是随着n的增加，时间复杂度和空间复杂度急剧增加，因为它包含了大量重复的计算。
通常情况下， 我们可以使用一个备忘录将已经计算过的房间保存起来，从而提升的代码效率，通常把这种递归称作带备忘录的递归。
修改代码如下：
说明两点：
1). 函数增加了一个参数memo，它是一个列表，用来保存f(i)的值；
2). 在计算f(i)的值时，如果不为0，说明已经计算过，直接返回memo[i]，否则就计算f(i)的值，再保存到memo[i]中，然后返回。
2. 动态规划
使用动态规划的思想是先定义一个列表dp[i]，表示从第一个房间开始到达第i个房间的最小跳跃次数，确定好初始状态，然后使用循环挨个求解，从而得到最终的结果。
其代码如下：
代码的意思和递归其实差不多，只是一个使用递归函数来计算f(i)，一个是使用循环来计算dp[i]。
至此，整个程序就全部完成了，你可以输入不同的数字来测试效果啦。
循环语句；
列表操作；
输入输出处理；
递归算法；
动态规划算法；
作为本次测评的最后一题，难度较大。关键点有两个，一是要彻底理解题目的意思，找到正确的解决方案，二是要善于将新问题转换为我们熟悉的问题，从而简化问题。
针对第一点，我们需要多列举几组不同特点的数据来进行分析测试，看看到底有什么规律，适合哪种算法。
对于求最值问题，常见的解决方案就是暴力枚举、贪心算法和动态规划，找到正确的方案至关重要了，一旦方向弄错了，后面的努力就都白费了。
针对第二点，这涉及到一个非常重要的学习理念--关联学习，什么样的学习最轻松、最有效，关联学习绝对是排得上号的。
一旦将本题和斐波那契数列关联起来，你会有一种豁然开朗的感觉，思路一下子完全打开了，这就是我们为什么要学习经典算法、经典案例的原因。
关于本题中使用的递归算法和动态规划算法，看起来完全不同，实际上关系非常密切。
它们有着相同的推导公式，有着相同的初始状态，所不同的是递归算法采取的是自顶向下，而动态规划采取的是自底向上。
实际上，凡是可以使用动态的地方，都可以使用递归算法来实现，而且强烈建议大家对于这类问题，一定要尝试使用两种算法来实现。
你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。
需要源码的，可以添加本人微信。
另外，超平老师创建了一个蓝桥杯备考交流群，这是专门为老师和家长打造的免费社群，您可以与来自全国各地的老师、家长共同交流经验，分享学习心得。
超平老师也会给大家带来及时的赛事动态，备考攻略，真题资源分享，帮助各位更好地备考第15届蓝桥杯赛事，力争取得优异的成绩。
扫码或长按加入微信群
