查看: 1265| 回复: 0
跳转到指定楼层
上一主题 下一主题
收起左侧

[学Python/Perl] 请教, 关于best time to buy and sell stock iv

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
https://leetcode.com/problems/be ... -stock-iv/solution/

这道题, 看了leetcode官方的解体思路, 基本上是3维dp, 也可以说成2维, 因为第3维只有0或1两种可能。dp表示: dp[day_number][used_transaction_number][stock_holding_status] . 但是有一点不太理解, 它说如果buying, 状态转移方程是dp[i][j][1]=dp[i-1][j-1][0]+prices[i], 我的理解是截止第i-1天一共做了j-1次交易, 第i-1天时未持有股票, 第i天做了买入操作, 那么截止第i 天一共做了j次操作, 获得的总利润是截止第i-1天获得的利润减去prices[i], 也就是第i天买入股票的钱, 这个能明白; 但是关于sellling, 官方给出的公式是dp[i][j][0]=dp[i-1][j][1]+prices[i], 我就不太明白, 按照上面buying的思路, 不应该是dp[i][j][0]=dp[i-1][[1]+prices[i]吗? 为什么取dp[i-1][j][1] instead of dp[i-1][j-1][1]? 如果截止第i-1天已经完成了j次操作, 那么第i天就没法再做一次操作了啊? 而且我理解dp[i-1][j][1] 的意思是在截止第i-1天还hold着股票, 那么必须在第i天有个卖出的操作, 不知道我理解的对吗? 求大神解惑。。。谢谢!


Buying, when j>0:
dp[i][j][1] = dp[i-1][j-1][0]-prices[i】

Selling:
dp[i][j][0] = dp[i-1][j][1]+prices[i】

官方完整代码:
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)

        # solve special cases
        if not prices or k==0:
            return 0

        if 2*k > n:
            res = 0
            for i, j in zip(prices[1:], prices[:-1]):
                res += max(0, i - j)
            return res

        # dp[i][used_k][ishold] = balance
        # ishold: 0 nothold, 1 hold
        dp = [[[-math.inf]*2 for _ in range(k+1)] for _ in range(n)]

        # set starting value
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]

        # fill the array
        for i in range(1, n):
            for j in range(k+1):
                # transition equation
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])
                # you can't hold stock without any transaction
                if j > 0:
                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])

        res = max(dp[n-1][j][0] for j in range(k+1))
        return res




上一篇:二分法求解 658. Find K Closest Elements
下一篇:LC257一个Go的问题
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表