leetcode 121. Best Time to Buy and Sell Stock

发布于:2025-04-16 ⋅ 阅读:(32) ⋅ 点赞:(0)

题目描述

本题属于动态规划类问题。

dp数组的含义

dp[i][0]表示从第0天到第i天为止,处于持有股票的状态下,账户里的最大金额。

dp[i][1]表示从第0天到第i天为止,处于不持有股票的状态下,账户里的最大金额。

按照这个定义dp[n-1][1]就是问题的答案。

dp数组的初始化

        dp[0][0] = -prices[0]; //表示买入了第0天的股票,手里账户金额是负数

        dp[0][1] = 0;  //表示到第0天为止,不持有股票即不买入第0天的股票的话,账户金额是0

递推公式的分析

从第0天到第i天为止,导致持有股票的状态有两种可能的原因:一是第0天到第i-1天的某一天买入了股票,对应dp[i-1][0]。二是第i天买入了股票,需要支付prices[i]。

            dp[i][0] = max(dp[i-1][0],-prices[i]);

从第0天到第i天为止,导致不持有股票的状态有两种可能的原因:一是从第0天到第i-1天为止就是不持有股票的状态(此情况下,第i天没法卖出股票)。二是第i天卖出了股票,第i天能卖出股票的前提是从第0天到第i-1天为止是持有股票的状态。

            dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        //dp[i][0]表示从第0天到第i天为止,处于持有股票的状态下,账户里的最大金额
        //dp[i][1]表示从第0天到第i天为止,处于不持有股票的状态下,账户里的最大金额
        vector<vector<int>> dp(n);
        for(int i = 0;i < n;i++){
            dp[i].resize(2);
        }
        dp[0][0] = -prices[0]; //表示买入了第0天的股票,手里账户金额是负数
        dp[0][1] = 0;  //表示到第0天为止,不持有股票即不买入第0天的股票的话,账户金额是0
        for(int i = 1;i < n;i++){
            //从第0天到第i天为止,导致持有股票的状态有两种可能的原因,
            //一是第0天到第i-1天的某一天买入了股票,对应dp[i-1][0]
            //二是第i天买入了股票,需要支付prices[i]
            dp[i][0] = max(dp[i-1][0],-prices[i]);
            //从第0天到第i天为止,导致不持有股票的状态有两种可能的原因:
            //一是从第0天到第i-1天为止就是不持有股票的状态(此情况下,第i天没法卖出股票)
            //二是第i天卖出了股票,第i天能卖出股票的前提是从第0天到第i-1天为止是持有股票的状态
            dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到