题解 | #商品交易#

题目链接

商品交易

题目描述

珐达采按顺序经过 n 个国家，在第 i 个国家，某种商品的价格为 A[i]。在每个国家，他可以做三件事之一：

花费 A[i] 买入一件商品。
卖出一件手中的商品，获得 A[i]。
什么都不做。

限制条件是：他手中最多只能持有一件商品。

求两个目标：

他能获得的最大总收益是多少。
在获得最大收益的前提下，最少的交易次数是多少。

解题思路

这是一个典型的动态规划问题，类似于“买卖股票”系列问题。我们需要同时优化两个目标：最大化收益和最小化交易次数。

1. 第一部分：最大化收益

我们可以定义两个DP状态数组：

dp[i][0]：表示在第 i 天（访问第 i 个国家）结束后，未持有商品时能获得的最大收益。
dp[i][1]：表示在第 i 天结束后，持有商品时能获得的最大收益。

状态转移方程：

对于 dp[i][0] (第 i 天未持有)：
- 可能是第 i-1 天就未持有，第 i 天什么都不做。收益为 dp[i-1][0]。
- 可能是第 i-1 天持有，第 i 天卖出。收益为 dp[i-1][1] + A[i]。
- 所以，dp[i][0] = max(dp[i-1][0], dp[i-1][1] + A[i])。
对于 dp[i][1] (第 i 天持有)：
- 可能是第 i-1 天就持有，第 i 天什么都不做。收益为 dp[i-1][1]。
- 可能是第 i-1 天未持有，第 i 天买入。收益为 dp[i-1][0] - A[i]。
- 所以，dp[i][1] = max(dp[i-1][1], dp[i-1][0] - A[i])。

基本情况：

dp[0][0] = 0 (第一天之前，未持有，收益为0)。
dp[0][1] = -A[0] (在第一天买入)。

最终的最大收益是在 n 天结束后，未持有商品时的收益，即 dp[n-1][0]。

2. 第二部分：最小化交易次数

为了在最大化收益的同时最小化交易次数，我们需要在DP状态中增加一个维度来记录交易次数。

dp[i][0] = {profit, trades} (第 i 天未持有，最大收益及对应最少交易次数)
dp[i][1] = {profit, trades} (第 i 天持有，最大收益及对应最少交易次数)

状态转移（带交易次数）：

计算 dp[i][0]：
- option1 = dp[i-1][0] (不操作)
- option2 = {dp[i-1][1].profit + A[i], dp[i-1][1].trades + 1} (卖出)
- dp[i][0] 的选择逻辑：
  - 如果 option1.profit > option2.profit，选 option1。
  - 如果 option2.profit > option1.profit，选 option2。
  - 如果收益相等，选交易次数少的那个。
计算 dp[i][1]：
- option3 = dp[i-1][1] (不操作)
- option4 = {dp[i-1][0].profit - A[i], dp[i-1][0].trades + 1} (买入)
- dp[i][1] 的选择逻辑与上面类似。

基本情况（带交易次数）：

dp[0][0] = {0, 0}
dp[0][1] = {-A[0], 1}

最终答案就是 dp[n-1][0] 中存储的收益和交易次数。

空间优化：注意到 dp[i] 的计算只依赖于 dp[i-1]，我们可以使用两个变量（或一个大小为2的数组）来代替DP数组，将空间复杂度从 $\mathcal{O}(N)$ 优化到 $\mathcal{O}(1)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct State {
    long long profit;
    int trades;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 0) {
        cout << "0 0" << endl;
        return 0;
    }

    State dp0 = {0, 0}; // State for not holding
    State dp1 = {-a[0], 1}; // State for holding

    for (int i = 1; i < n; ++i) {
        State prev_dp0 = dp0;
        State prev_dp1 = dp1;

        // Calculate new dp0
        long long profit_sell = prev_dp1.profit + a[i];
        if (profit_sell > prev_dp0.profit) {
            dp0 = {profit_sell, prev_dp1.trades + 1};
        } else if (profit_sell == prev_dp0.profit) {
            dp0 = {profit_sell, min(prev_dp1.trades + 1, prev_dp0.trades)};
        } else {
            dp0 = prev_dp0;
        }

        // Calculate new dp1
        long long profit_buy = prev_dp0.profit - a[i];
        if (profit_buy > prev_dp1.profit) {
            dp1 = {profit_buy, prev_dp0.trades + 1};
        } else if (profit_buy == prev_dp1.profit) {
            dp1 = {profit_buy, min(prev_dp0.trades + 1, prev_dp1.trades)};
        } else {
            dp1 = prev_dp1;
        }
    }

    cout << dp0.profit << " " << dp0.trades << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    static class State {
        long profit;
        int trades;

        State(long profit, int trades) {
            this.profit = profit;
            this.trades = trades;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        if (n == 0) {
            System.out.println("0 0");
            return;
        }

        State dp0 = new State(0, 0); // Not holding
        State dp1 = new State(-a[0], 1); // Holding

        for (int i = 1; i < n; i++) {
            State prevDp0 = dp0;
            State prevDp1 = dp1;

            // Calculate new dp0 (not holding)
            long profitSell = prevDp1.profit + a[i];
            if (profitSell > prevDp0.profit) {
                dp0 = new State(profitSell, prevDp1.trades + 1);
            } else if (profitSell == prevDp0.profit) {
                dp0 = new State(profitSell, Math.min(prevDp1.trades + 1, prevDp0.trades));
            } else {
                dp0 = prevDp0;
            }

            // Calculate new dp1 (holding)
            long profitBuy = prevDp0.profit - a[i];
            if (profitBuy > prevDp1.profit) {
                dp1 = new State(profitBuy, prevDp0.trades + 1);
            } else if (profitBuy == prevDp1.profit) {
                dp1 = new State(profitBuy, Math.min(prevDp0.trades + 1, prevDp1.trades));
            } else {
                dp1 = prevDp1;
            }
        }

        System.out.println(dp0.profit + " " + dp0.trades);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return
        n = int(n_str)
        if n == 0:
            print("0 0")
            return
        
        a = list(map(int, sys.stdin.readline().split()))
        
        # dp0: [profit, trades] for not holding
        # dp1: [profit, trades] for holding
        dp0 = [0, 0]
        dp1 = [-a[0], 1]
        
        for i in range(1, n):
            prev_dp0 = dp0[:]
            prev_dp1 = dp1[:]
            
            # Calculate new dp0
            profit_sell = prev_dp1[0] + a[i]
            if profit_sell > prev_dp0[0]:
                dp0 = [profit_sell, prev_dp1[1] + 1]
            elif profit_sell == prev_dp0[0]:
                dp0 = [profit_sell, min(prev_dp1[1] + 1, prev_dp0[1])]
            else:
                dp0 = prev_dp0

            # Calculate new dp1
            profit_buy = prev_dp0[0] - a[i]
            if profit_buy > prev_dp1[0]:
                dp1 = [profit_buy, prev_dp0[1] + 1]
            elif profit_buy == prev_dp1[0]:
                dp1 = [profit_buy, min(prev_dp0[1] + 1, prev_dp1[1])]
            else:
                dp1 = prev_dp1
                
        print(f"{dp0[0]} {dp0[1]}")

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：动态规划
时间复杂度: $\mathcal{O}(N)$ 。我们只需要对价格数组进行一次线性扫描。
空间复杂度: $\mathcal{O}(1)$ 。通过使用常量个变量来存储前一天的状态，我们将空间复杂度从 $\mathcal{O}(N)$ 优化到了 $\mathcal{O}(1)$ 。