Python动态规划

解题思路:单纯用递归会超时，采用动态规划，状态转移方程就是递归方程，可以一步到位

注意事项:
从1开始计数，dp[0]没有用到
参考代码:

def sw_ap(s, n, a):      # 用a替换s中n位置的元素
   s[n] = a


dp = [1, 1, 2, 3, 4]
for i in range(51):
   dp.append(0)
for t in range(5, 56):
   a = dp[t - 1] + dp[t - 3]
   sw_ap(dp, t, a)
for i in range(1, 56):
   n = int(input())
   if n == 0:
       break
   else:
       print(dp[n])