Python: 求解数组中不相邻元素之和的最大值（动态规划法）

Exploring

发布于 2022-09-20 14:01:27

1.8K0

发布于 2022-09-20 14:01:27

文章背景：最近在学习动态规划的相关知识，在网上也看了不少资料。动态规划法，是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

有一道题是这样的：在一维数组arr中，找出一组不相邻的数字，使得最后的和最大。比如：有个数组arr为[1, 2, 4, 1, 7, 8, 3]，那么最优的结果为 1 + 4 + 7 + 3= 15。

解题思路：针对数组内的每个数字，都存在选和不选的两种情况。对于最后一个数字3，如果选了3，则8就不能选，再继续判断前两位，也就是7的情况。如果不选3，则直接判断前一位，也就是8的情况。每个数字都有选和不选两种可能，选取这两种情况中的最佳解。

对于一维数组arr(下标从0开始)，到达第i个数字为止的最优解记为OPT(i)，则

代码实现：

（1）递归法

# Recursive method;
# Codes found at：https://www.youtube.com/watch?v=Jakbj4vaIbE
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)

print(rec_opt(arr, len(arr)-1))

由于递归法的时间复杂度较大，下面介绍另一种方法。

（2）非递归法

# DP method;
# Codes found at：https://www.youtube.com/watch?v=Jakbj4vaIbE

import numpy as np
arr = [1,2,4,1,7,8,3]

def 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]

print(opt(arr))

注意: numpy为第三方库，调用前需要确保电脑上已经安装了numpy库。

参考资料：

[1] 动态规划(https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92)

[1] 数组不相邻元素之和的最大值(https://blog.csdn.net/csdn15698845876/article/details/88789357)

[2] 动态规划（第2讲）(https://www.youtube.com/watch?v=Jakbj4vaIbE)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除

https