奇安信 服务器开发 笔试 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"]