最大股票收益

Submission

运行时间: 567 ms

内存: 16.0 MB

class Solution:
    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:
        dp = [0]*(budget+1)
        for p, f in zip(present, future):
            if f <= p: continue
            for b in range(budget, p-1, -1):
                dp[b] = max(dp[b], dp[b-p] + f - p)
        return dp[budget]


        # M[n][b] = max(M[n-1][b], M[n-1][b-p[n]] + f[n]-p[n])

Explain

该题解采用了动态规划的方法来解决问题。定义一个dp数组来存储达到不同预算条件下的最大利润。数组的每个元素dp[b]表示在预算b下能够获得的最大利润。对于每一对当前价格p和未来价格f，如果未来价格f大于当前价格p（即只有在有利润的情况下才进行考虑），则遍历预算从高到低，尝试在购买这个股票后更新最大利润。更新策略是比较不买这个股票时的利润（dp[b]）与买了这个股票后的利润（dp[b-p] + f - p）的较大值。

时间复杂度: O(n*budget)

空间复杂度: O(budget)

class Solution:
    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:
        dp = [0]*(budget+1)  # 创建一个长度为budget+1的dp数组，初始化为0
        for p, f in zip(present, future):  # 遍历每个股票的当前价格和未来价格
            if f <= p: continue  # 如果未来价格不高于当前价格，则跳过
            for b in range(budget, p-1, -1):  # 从预算上限到当前价格遍历，尝试买入股票
                dp[b] = max(dp[b], dp[b-p] + f - p)  # 更新在预算b下的最大利润，考虑买或不买当前股票
        return dp[budget]  # 返回最大预算下的最大利润

Explore

在动态规划中，从预算的上限向下遍历是为了防止同一轮循环中对dp数组的先前元素进行重复更新。如果从当前价格向上遍历，那么低预算的dp值可能被高预算情况下计算的结果影响，从而导致逻辑错误。具体地，当我们考虑购买一个股票时，预算减少，但如果从低到高更新，则可能用已经假设购买了该股票的预算状态去更新更高的预算状态，这实际上是错误的。因此，从高到低遍历可以确保每个预算状态是独立计算，没有被前面的状态影响。

由于我们是从预算的上限向下遍历的，当处理到预算b时，dp[b-p]代表的是在更低的预算下，不受当前预算购买决策影响的最大利润状态。这是因为我们从高到低更新预算，所以当我们更新dp[b]时，dp[b-p]已经是固定下来的，并不会在本次循环中被修改。这确保了数据的正确性和独立性。

算法在这种情况下仍然是有效的，并不会导致重复计算同一种可能性。尽管多个股票可能有相同的购买和销售价格，但每次处理一个股票时，都是基于当前的dp数组状态来决定是否购买，以及购买后的最大利润。即使价格相同，不同股票的处理是独立的，并不会互相影响已经计算的结果。

当股票的未来价格小于或等于当前价格时，从这个股票中获得正收益是不可能的，因为我们不能从买入价格更高或相等然后卖出获得利润。因此，在这种情况下跳过处理是合理的，它不会错过任何利润机会，反而可以避免不必要的计算。这种处理方式是基于问题的基本经济逻辑：没有利润的交易是不值得执行的。