奇安信 服务器开发 笔试 python
第一题：力扣原题 473. 火柴拼正方形
第二题：零钱兑换 小修
def maxIncomeProducts(products, months):
if months == 0:
return []
n = len(products)
temp = []
for i in range(n+1):
temp.append({"Val": 0, "Info": []})
dp = []
for i in range(months+1):
dp.append(temp[:])
products.sort(key=lambda p: p.x)
for i in range(1, months+1):
for j in range(1, n+1):
if i < products[j-1].x:
if dp[i][j-1]["Val"] >= dp[i][j]["Val"]:
dp[i][j]["Val"] = dp[i][j-1]["Val"]
dp[i][j]["Info"] = dp[i][j-1]["Info"][:]
else:
if dp[i-products[j-1].x][j]["Val"]+products[j-1].y > dp[i][j-1]["Val"]:
dp[i][j]["Val"] = dp[i-products[j-1].x][j]["Val"] + products[j-1].y
dp[i][j]["Info"] = dp[i-products[j-1].x][j]["Info"][:] + [products[j-1]]
else:
if dp[i][j-1]["Val"] > dp[i][j]["Val"]:
dp[i][j]["Val"] = dp[i][j-1]["Val"]
dp[i][j]["Info"] = dp[i][j-1]["Info"][:]
return dp[months][n]["Info"]
类似资料：