题目：求解一个数组中不相邻元素的最大和

分析：首先从最后一个元素开始分析，如果选最后一个元素的话，就不能选倒数第二个元素，这时要考虑OPT(n)=max(OPT(n-2)+arr[n], OPT(n-1)),这个就是递归的公式，然后设计递归出口，当n=1时 上面的式子不成立，OPT(1)=max(arr[0],arr[1]),当n=2时，OPT[2] = max(arr[0],arr[1])

递归代码

arr = [1,2,4,1,7,8,3]
def rec_opt(arr,i):
    if i==0:
        return arr[0]
    elif i==1:
        return max(arr[0],arr[1])
    else:
        A = rec_opt(arr,i-2)+arr[i]
        B = rec_opt(arr,i-1)
        return max(A,B)

res = rec_opt(arr,6)
print(res)

动态规划解法

设计一个数组，从头到尾计算OPT，并保存在数组内

import numpy as np
def dp_opt(arr):
    opt = np.zeros(len(arr))
    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]