[刷题笔记] Best Time to Buy and Sell Stock III

  1. 1. 题目
  2. 2. 思路
  3. 3. TimeOut的提交
  4. 4. Accepted

题目

思路

主体思想还是动态规划。

如何写出状态矩阵。dp ?

1
2
3
4
5
dp[i][j][k]

i: 当前prices中的第i个元素
j: 还可以出售j次, j in [0,1,2]
k: 0 表示持有股票状态，1 表示不持有股票状态

注意这里的j表示的是可以出售的次数。所以在状态转移的过程中，买入不需要减少j，只有出售时候需要变动。

接下来就是状态转移矩阵

1
2
3
4
5
6
for i in 1...prices.length
    for j in 0..1
        dp[i][j][0] = max(dp[i-1][j+1][1]+prices[i], dp[i-1][j][0])
        dp[i][j][1] = max(dp[i-1][j][0] - prices[i], dp[i-1][j][1])
    end
end

以及初始状态

1
2
3
4
dp[0][0][0] = 0
dp[0][0][1] = - 1 * prices[0]
dp[0][1][0] = 0
dp[0][1][1] = -1 * prices[0]

当然还需要更多初始状态

1
2
3
4
5
for i in 0...prices.length
    dp[i][0][0] = 0
    dp[i][2][0] = 0
    dp[i][2][1] = -1 * min_of(prices)
end

TimeOut的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def max_profit(prices)
    dp = Array.new(prices.length){Array.new(3){Array.new(2)}}
    # 2 digial can sell count
    dp[0][0][0] = 0
    dp[0][0][1] = - 1 * prices[0]
    dp[0][1][0] = 0
    dp[0][1][1] = -1 * prices[0]
    
    for i in 0...prices.length
       min = prices[i] if  prices[i] < min
        dp[i][0][0] = 0
        dp[i][2][0] = 0
        dp[i][2][1] = -1 * prices[0..i].sort.first
    end
    
    
    for i in 1...prices.length
        for j in 0..1
            dp[i][j][0] = max(dp[i-1][j+1][1]+prices[i], dp[i-1][j][0])
            dp[i][j][1] = max(dp[i-1][j][0] - prices[i], dp[i-1][j][1])   
        end
    end
    
    return dp[prices.length - 1][0][0]
    
    
end

Timeout的原因在于dp[i][2][1] = -1 * prices[0..i].sort.first, 其实我们在遍历的时候可以顺便求最小值。

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def max_profit(prices)
    dp = Array.new(prices.length){Array.new(3){Array.new(2)}}
    # 2 digial can sell count
    dp[0][0][0] = 0
    dp[0][0][1] = - 1 * prices[0]
    dp[0][1][0] = 0
    dp[0][1][1] = -1 * prices[0]
    
    min = prices[0]
    for i in 0...prices.length
       min = prices[i] if  prices[i] < min
        dp[i][0][0] = 0
        dp[i][2][0] = 0
        dp[i][2][1] = -1 * min
    end
    
    
    for i in 1...prices.length
        for j in 0..1
            dp[i][j][0] = max(dp[i-1][j+1][1]+prices[i], dp[i-1][j][0])
            dp[i][j][1] = max(dp[i-1][j][0] - prices[i], dp[i-1][j][1])   
        end
    end
    
    return dp[prices.length - 1][0][0]
    
    
end


def max(a,b)
    return a > b ? a : b
end
刷题
如果你觉得本文对你有帮助，请给我点赞助。