题解 | #牛群买卖计划II# 状态机DP

牛群买卖计划II

https://www.nowcoder.com/practice/3fa6bc9c3a724b4089eea26d3f87171b

知识点

状态机DP

思路

定义 f[i][j][st] 前i天完成j笔交易,手上股票持有状态为st 的价值最大值。状态转移可以分为当前股票保持或者卖出两种状态,就可以进行转移。答案为前n天手上持有状态为0的最大值。时间复杂度O(nk)

AC Code(C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @param k int整型 
     * @return int整型
     */
    const int INF = 0x3f3f3f3f;
    int f[100010][110][2];
    int maxProfitII(vector<int>& prices, int k) {
        int n = prices.size();
        for (int i = 0; i <= k; i ++) {
            f[0][i][0] = f[0][i][1] = -INF;
        }
        f[0][0][0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= k; j ++) {
                // 不动 / 进行买卖
                f[i][j][0] = max(f[i - 1][j][1] + prices[i - 1], f[i - 1][j][0]);
                f[i][j][1] = max(f[i - 1][j - 1][0] - prices[i - 1], f[i - 1][j][1]);
            }
        }
        int res = 0;
        for (int i = 0; i <= k; i ++) {
            res = max(res, f[n][i][0]);
        }
        return res;
    }
};

全部评论

相关推荐

06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务