动态规划买卖股票的最佳时机介绍

动态规划买卖股票的最佳时机是一个经典的算法问题。该问题的目标是在给定的股票价格数组中，找到最大的利润，即最佳的买入和卖出时间，使得买入时间早于卖出时间。

动态规划算法解决该问题的思路是：用一个数组记录每天的股票价格，从前往后扫描，用一个变量记录截至当前天数的最小股票价格，同时用另一个数组记录截至当前天数卖出所能得到的最大利润。当扫描到第 i 天时，更新最小股票价格和最大利润数组，最终得到的最大利润即为买卖股票的最佳时机。

相关问题

动态规划实现买卖股票的最佳时间

动态规划可以用来实现买卖股票的最佳时间。下面是一个动态规划的实现方法：

1. 定义状态：
- `dp[i][j][k]` 表示第 i 天，进行了 j 次交易，持有状态为 k（0 表示未持有，1 表示持有）时的最大利润。

2. 初始化状态：
- `dp[j] = 0`，第 0 天未进行交易且未持有股票时的利润为 0。
- `dp[j] = -prices`，第 0 天未进行交易但持有股票时的利润为负的股票价格。

3. 状态转移方程：
- `dp[i][j] = max(dp[i-1][j][0], dp[i-1][j] + prices[i])`，第 i 天未持有股票的最大利润等于前一天未持有股票的最大利润和前一天持有股票但在第 i 天卖出的最大利润的较大值。
- `dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])`，第 i 天持有股票的最大利润等于前一天持有股票的最大利润和前一天未持有股票但在第 i 天买入的最大利润的较大值。

4. 最终结果：
- 最大利润为 `dp[n-1][k]`，其中 n 是天数，k 是最大交易次数。

下面是一个示例代码：

def maxProfit(prices, k):
    n = len(prices)
    if k > n // 2:
        # 如果 k 大于 n 的一半，相当于可以进行任意多次交易
        return maxProfitUnlimited(prices)
    
    dp = [[[0] * 2 for _ in range(k+1)] for _ in range(n)]
    
    for i in range(n):
        for j in range(k, 0, -1):
            if i == 0:
                dp[i][j][0] = 0
                dp[i][j][1] = -prices[i]
            else:
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
    
    return dp[n-1][k][0]

def maxProfitUnlimited(prices):
    n = len(prices)
    dp = [[0] * 2 for _ in range(n)]
    
    for i in range(n):
        if i == 0:
            dp[i][0] = 0
            dp[i][1] = -prices[i]
        else:
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    
    return dp[n-1][0]

动态规划实现买卖股票的最佳时间（C）

动态规划可以用来实现买卖股票的最佳时间。下面是一个使用动态规划解决该问题的C代码示例：

#include <stdio.h>
#include <stdlib.h>

int maxProfit(int* prices, int pricesSize) {
    if (pricesSize <= 1) {
        return 0;
    }
    
    int* dp = (int*)malloc(pricesSize * sizeof(int));
    dp[0] = 0;
    int minPrice = prices[0];
    
    for (int i = 1; i < pricesSize; i++) {
        dp[i] = dp[i-1] > prices[i] - minPrice ? dp[i-1] : prices[i] - minPrice;
        minPrice = minPrice < prices[i] ? minPrice : prices[i];
    }
    
    int maxProfit = dp[pricesSize-1];
    free(dp);
    
    return maxProfit;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int pricesSize = sizeof(prices) / sizeof(prices[0]);
    
    int result = maxProfit(prices, pricesSize);
    printf("Max profit: %d\n", result); // 输出：5
    
    return 0;
}

该代码中，我们使用一个动态规划数组dp来记录每一天的最大利润。我们同时使用一个变量minPrice来记录当前的最低股价。在遍历股价数组时，我们更新dp数组和minPrice，最后返回dp数组的最后一个元素作为最大利润。