当前子状态选和不选的问题，
从后面往前面推：
当前A状态选：A以前的最佳状态B+A状态的值
当前A状态不选：A-1状态
代码编写：
状态用函数编写
用一个数据来存放每一个当前的最佳状态（即函数）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
例题：leetcode--198.打家劫舍
https://leetcode-cn.com/problems/house-robber/
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
设当前状态为opt(i)
则在arr = [1,2,4,1,7,8,3]当中
对于opt(4)
选择opt(4) ：opt(2)+arr[i]
不选择opt(4) : opt(3)
则最佳选择为 max( opt(2)+arr[i] , opt(3) )
opt(i).....opt(0)根据这样的规则类推
需要注意的是，要找到递归的出口：
opt(0）= arr[0]
opt(1) = max(arr[0],arr[1])
可得通项为：
opt = max(opt(i-2)+arr[i],opt(i-1)), i>1
= max(arr[i]) i<0
代码如下：
import numpy as np
#递归实现
arr = [1,2,4,1,7,8,3]
def dec_opt(arr,i):
if i == 0:
return arr[0]
elif i == 1:
return max(arr[0],arr[1])
else:
a = dec_opt(arr,i - 2) + arr[i]
b = dec_opt(arr,i - 1)
return max(a,b)
print(dec_opt(arr,6))
#非递归实现
def dp_opt(arr):
opt = np.zeros(len(arr))#创建一个和arr[]一样长且全为0的数组
opt[0] = arr[0]
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]
print(dp_opt(arr))
结果：
15
15.0
