Leetcode中的股票买卖问题

Question

波波老师好！我发现Leetcode共有如下stoclk buy and sell问题:

1. 121. Best Time to Buy and Sell Stock (easy)
2. 122. Best Time to Buy and Sell Stock II (Medium)
3. 123. Best Time to Buy and Sell Stock III (Hard)
4. 309. Best Time to Buy and Sell Stock with Cooldown (Medium)

如果用dfs + memoization的方法，我发现可以用基本相同的思路来处理。不同的是，需要根据不同约束条件进行调整。我的问题主要在121和123题，不知道我是否遗漏了啥。对于LC 123题，我的解如下：

class Solution {
    Integer[][][] memo;
    public int maxProfit(int[] prices) {
        memo = new Integer[prices.length][2][3];
        return dfs(prices, 0, 0, 0);
    }
    private int dfs(int[] prices, int day, int hasStock, int times) {
        if (day >= prices.length) {
            return 0;
        }
        if (memo[day][hasStock][times] != null){
            return memo[day][hasStock][times];
        }
        int profit = dfs(prices, day + 1, hasStock, times);

        if (hasStock == 1) {
            profit = Math.max(profit, dfs(prices, day + 1, 0, times + 1) + prices[day]);
        } else if (times < 2) {
            profit = Math.max(profit, dfs(prices, day + 1, 1, times) - prices[day]);
        }

        return memo[day][hasStock][times] = profit;
    }
}

我的问题主要有两个：

• 对于LC121来说，可以套用LC123的代码，唯一需要变的是memo= new Integer[prices.length][2][1], 也就是times的约束变成了1次，即最多进行一次交易。因为LC121标明的是easy，不知道我对这个问题的理解是否过于复杂了？
• 第二个问题是关于时间复杂度，虽然这个问题也是O(n)的线性时间复杂度，但是和非递归的DP方法比要慢很多，在我提交记录里，这个方法的runtime是143ms，而DP只有2ms。这个是因为递归所导致的吗？以下是我的DP代码：

class Solution {
    public int maxProfit(int[] prices) {
        
        

        int heldOne = Integer.MIN_VALUE;
        int soldOne = 0;
        int heldTwo = Integer.MIN_VALUE;
        int soldTwo = 0;
        
        for (int i = 0; i < prices.length; i++) {
            
            int tempHeldOne = heldOne;
            int tempSoldOne = soldOne;
            int tempHeldTwo = heldTwo;
            int tempSoldTwo = soldTwo;
            
            heldOne = Math.max(tempHeldOne, -prices[i]);
            soldOne = Math.max(tempSoldOne, tempHeldOne + prices[i]);
            heldTwo = Math.max(tempHeldTwo, tempSoldOne - prices[i]);
            soldTwo = Math.max(tempSoldTwo, tempHeldTwo + prices[i]);
            
        }
        
        return Math.max(soldTwo, soldOne);
    }
    
}

Answer 1

liuyubobobo 2023-08-21 17:03:28

先说个无关的，这个问题我这边一直无法通过审核，如图所示。今天找慕课网的工作人员才解决。

==========

1)

121 不需要 dp，有更简单的解法。

因为只需要一次买卖，所以只需要枚举卖的时间点，买的时间肯定是之前价格的最小值。所以只需要遍历记录当前价格的最小值即可。O(n) 的时间，O(1) 的空间。

（从后往前，枚举买的时间，记录卖的最高价格也可以。）

2）

不仅仅是递归，你给出的 dp 代码还做了空间优化（只用了 O(1) 的空间。）

在一个高维数组中做寻址也是很花时间的。

你可以比较一下，使用 dp，但是空间是 O(n)，看一下性能差距。

继续加油！：）