NC134 股票(无限次交易)

描述

假定你知道 n 天内的某只股票每一天价格的变动。你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。

1. 动态规划

观察本题的性质，每一天的最优收益，与前面的某一天的收益无关，只和前面所有天的最优收益有关系，体现了动态规划的无后效性，因此本题适用动态规划。

本题涉及了2个状态的互相转移，因此需要用状态机类型的dp。

设 $d p [i] [0], d p [i] [1]$ 分别表示截止到第i天，你持有股票和不持有股票的最优解，那么有如下关系：

$d p [i] [0] = m a x (d p [i - 1] [0], d p [i - 1] [1] - p [i])$ , 你第i天有股票，那么有可能是前一天也有股票，今天不操作，也可能是昨天没有股票，今天花 $p [i]$ 的钱买进，取这两种情况的最优解。
$d p [i] [1] = m a x (d p [i - 1] [1], d p [i - 1] [0] + p [i]])$ , 你第i天没有股票，有可能你昨天也没有，继续空仓，也可能昨天有，今天卖了 $p [i]$ 元，取两种情况最大值

那么，答案就是 $d p [n] [1]$ ，因为最后一天肯定要把股票卖了

初值是dp[1][0] = -p[1], dp[1][1] = 0，根据题意很好理解。

为了实现题目要求的空间复杂度常数，我们可以观察dp转移式的性质，发现可以压缩一维。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    
   
    int maxProfit(vector<int>& p) {

        int n = p.size();
        if (n == 0) return 0;

        int dp0 = -p[0], dp1 = 0;
        
        for (int i = 1; i < n; i++) {
            int last0 = dp0, last1 = dp1;
            dp0 = max(last0, last1 - p[i]);
            dp1 = max(last1, last0 + p[i]);
        }
        return dp1;
    }
};

时间复杂度： $O (n)$ , 一重循环
空间复杂度： $O (1)$ , DP数组压缩后变为常数空间。

2. 贪心

考虑贪心性质，如果今天价格比昨天高，那么我就昨天买今天卖，赚两天的差价，否则不操作。

如果把数组值看做纵轴，下标看做横轴，画一条折线，实际就等价于求折线上升部分的总和。 alt 如图所示，求所有红色部分即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int res = 0, last = INT_MAX;
        for (int i : prices) {
            // 能赚，就加上
            res = i>last ? res+i-last : res;
            last = i;
        }
        return res;
    }
};

时间复杂度： $O (n)$ , 一重循环
空间复杂度： $O (1)$ , 常数个变量

题解 | #股票(无限次交易)#

NC134 股票(无限次交易)

描述

1. 动态规划

2. 贪心