打家劫舍问题：一个凶猛的悍匪，潜伏在一条繁华的大gai上，准备去偷，啊，不对，悍匪的事情怎么能够说偷呢？那叫悄悄滴抢，也不知道到时候能不能按抢劫来判。
好了，回归正题，悍匪发现相邻的房屋都被闯入的话房间就会报警，也不知道谁设计的。算一下悍匪没被抓的情况下，一晚上最多有多少“收获”。
就比如说：集合[16,30,18,24,22,22,23]求在相加元素不相邻的情况下，求最大，经过作者的大脑推算了整整一夜，算出当几个元素：16+18+22+23的情况最大，为79。
解析一下：每个像个元素之间最少隔一个元素，最多个两个元素，为什么最多是两个元素呢？如果隔了三个元素的话就浪费了一个可以相加的元素。
所以这个问题也是比较简单的，因为元素间隔不是一就是两。可以用迭代和递归的方式实现，还有一种，额，手动穷举比较，但这也是比较慢的，递归也是比较占用CPU资源的，比较慢，所以我们主要采用的方法进行迭代算。
来，动态规划，迭代和递归都属于动态规划，但递归回产生大量重叠组问题，迭代和递归都会有：
先讲递归：
递归：
图源：咸鱼画的
递归示意图，可以观察到，这是一棵生长茁壮的“满二叉树”，空间复杂度2n时间复杂度2n十分恐怖，而递归的代码也是简单粗暴：
def solution(arr, i): # 递归求解函数
if i == 0:
return arr[0]
elif i == 1:
return max(arr[0], arr[1]) #排除两种情况
else:
a = solution(arr, i - 2) + arr[i] # a为选择数组最后一个元素，然后只能选第i-2个元素
b = solution(arr, i - 1) # b为不选最后一个元素，所以就选择第i-1个元素 return max(a, b)
return max(a,b)
arr = [80,75,87,78,77,86,88,79] #赋值arr做一个例子
result = solution(arr,len(arr)-1) #以arr计数长度为i值
print(result)
#最后一步如不不这样的话就会出现无返回值的错误。
分享一个踩过的坑：如果过度调用递归的话就会出现过Recursionerror，Python所能储存深度超出最大的错误，可以用import sys
sys. setrecursionlimit（9999999）#可变函数，但是如果写大了就会出现Segmention fault非法越界访问的问题，所以递归还是很脑壳痛的问题。
接下来是非递归的，也就是迭代，有一句话“人懂迭代，神懂递归”。
import numpy as np#也可以不用numpy手动写算法生成opt
def fishcode(arr):
opt = np.zeros(len(arr))#构建一个全部填0长度为arr长度的一维数组
opt[0] = arr[0] #重新构建opt
opt[1] = max(arr[0], arr[1]) #构建第二位
for i in range(2, len(arr)): #开始迭代运算
a = opt[i - 2] + arr[i] #第一种方式累加
b = opt[i - 1] #第二种方式累加
opt[i] = max(a, b)
return opt[len(arr)-1] #累加过后得到的最后一位便是最优解
arr = [14,13,17,19,29,23] #手动赋值做例子
result = fishcode(arr)
print(result)#和上面的一样原因
图源：咸鱼画的
可以看出来，迭代的运算是复杂度仅为O(n)
—————————————END———————————————
作者本想再写C语言版的，但当初学算法的时候买了Python算法书，对C语言递归与迭代算法了解尚浅，仅能写出一些简单递归，并不能为各位解读代码。
