文章背景：有一道题是这样的：给定一个一维数组arr，判断是否有一组数字加起来，正好等于s。比如：有个数组arr为[3, 34, 4, 12, 5, 2]，给定s=9。则给定数组内存在这样的数字，加起来正好等于9，比如3 4 2 = 9, 或 4 5 = 9。
解题思路：针对数组内的每个数字，都存在选和不选的两种情况。对于最后一个数字2，如果选了2，则继续判断2前面的几个数字是否可以加起来等于7（9-2=7）。如果不选2，则继续判断2前面的几个数字是否可以加起来等于9。每个数字都有选和不选两种可能，只要有一种情况满足要求（加起来正好等于s），则判定为True(存在)。
对于一维数组arr(下标从0开始)，假定数组内的所有数字都是正整数，给定的s也为正整数。记判定到第i个数字为止的结果记为subset(arr, i, s)，则
代码实现：
（1）递归法
代码语言：javascript复制# Recursive method;;
# Codes found at：https://www.youtube.com/watch?v=Jakbj4vaIbE
arr = [3,34,4,12,5,2]
def rec_subset(arr,i,s):
if s == 0:
return True
elif i == 0:
return arr[0] == s
elif arr[i] > s:
return rec_subset(arr,i-1,s)
else:
A = rec_subset(arr,i-1,s-arr[i])
B = rec_subset(arr,i-1,s)
return A or B
print(rec_subset(arr,len(arr)-1,9))由于递归法的时间复杂度较大，下面介绍另一种方法。
（2）非递归法
对于非递归法，需要创建一个二维数组subset(i,s)。其中的i代表各个数字在一维数组arr内的索引值。s代表给定值。
# DP method;
# Codes found at：https://www.youtube.com/watch?v=Jakbj4vaIbE
import numpy as np
arr = [3,34,4,12,5,2]
def dp_subset(arr,S):
subset = np.zeros((len(arr),S 1),dtype=bool)
subset[:,0] = True
subset[0,:] = False
subset[0,arr[0]] = True
for i in range(1,len(arr)):
for s in range(1, S 1):
if arr[i]>s:
subset[i,s] = subset[i-1,s]
else:
A = subset[i-1,s-arr[i]]
B = subset[i-1,s]
subset[i,s] = A or B
r,c = subset.shape
return subset[r-1,c-1]
print(dp_subset(arr,9)) 注意: numpy为第三方库，调用前需要确保电脑上已经安装了numpy库。
参考资料：
[1] 动态规划（https://zh.wikipedia.org/wiki/动态规划）
[1] 从简单例子 一步一步倒推 深入浅出动态规划算法的原理（https://blog.csdn.net/qq_33709508/article/details/104112314）
[2] 动态规划（第2讲）（https://www.youtube.com/watch?v=Jakbj4vaIbE）
延伸阅读：
[1] Python: 求解数组中不相邻元素之和的最大值（动态规划法）
