绿巨人吃饼

题目：绿巨人要吃m个饼，他一口可以吃1个或者2个饼，但是每次一口2个之后的连续两口只能一口1个。请问绿巨人有几种方式吃完m个饼？

分析：本题酷似动态规划爬楼梯的改编

递推前几项或画二叉树可知 m <= 5 时，f(m) = m；

每个饼有两种可能的吃法，单独吃下或双管(饼)奇下。双饼奇下: 吃了2个饼之后连续两口只能一口1个，反观历史：状态 dp[i-1]（吃1个）=dp[i-2]（吃1个）=dp[i-3]（吃2个）等价于dp[i-4]吃4个。故状态转移方程为：

dp[i] = dp[i-1] + dp[i-4], i>4

代码实现

# 动态规划
m = int(input()) # 输入非负整数m
dp = [i for i in range(0, m+1)] # 初始化dp数组(当 m <= 5 时，dp[i] = i)
for i in range(5, m+1): # 当 m >= 5 时，状态转移方程为：dp[i] = dp[i - 1] + dp[i - 4]
  dp[i] = dp[i - 1] + dp[i - 4]
print(dp[-1]) # 打印dp数组最后一个元素