昨天参加了一场网上技术面试，通过腾讯会议平台。面试官问了两道算法题，都没答上来，-_-||。看来自己必须要高度重视算法基础，多刷多积累算法题了。
面试结束后，自己在网上搜索了第一道题目以及其解法，才恍然大悟原来这就是动态规划，下面是题目介绍：
题目：将一个数组分成两部分，不要求两部分所包含的元素个数相等，要求使得这两个部分的和的差值最小。比如对于数组{1,0,1,7,2,4}，可以分成{1,0,1,2,4}和{7}，使得这两部分的差值最小。
当时面试官是口述这道题，我的理解应该是得到这两个数组的具体内容，而不仅仅是这其中的差值，而网上看到的解法基本上都是仅仅求得差值，所以自己在理解他人实现后增加了完整的代码，这里简单记录一下。同时激励自己多刷刷算法题呀！
def solution(arr):
target = sum(arr) // 2
# 初始化动态规划二维矩阵
matrix = [[0]*(target+1) for i in range(len(arr)+1)]
# 求解主算法
for i in range(1, len(arr)+1):
for j in range(1, target+1):
if j >= arr[i-1]:
matrix[i][j] = max(matrix[i-1][j], matrix[i-1][j-arr[i-1]] + arr[i-1])
else:
matrix[i][j] = matrix[i-1][j]
# 初始化两个数组
a = [] # 存储目标元素
b = [] # 存储其他元素
n = target
# 反向求解得到数组具体值
for m in range(len(arr), 0, -1):
if arr[m-1] <= n and matrix[m-1][n] < matrix[m-1][n-arr[m-1]] + arr[m-1]:
a.append(arr[m-1])
n -= arr[m-1]
else:
b.append(arr[m-1])
return matrix[-1][-1], a, b
arr = [1, 0, 1, 7, 2, 4]
res = solution(arr)
print(res)
参考
- 0-1背包问题及Python代码实现 - 简书
- 将数组分成两部分，使得这两部分的和的差最小_C/C++_Swartz2015的专栏-CSDN博客
- 数组分为两部分，使得其和相差最小 - ranjiewen - 博客园
- 把一个数组分为两部分使得其和相差最小 - 知乎
