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