C语言的dp算法LeetCode炒股习题案例分析

# C语言的dp算法LeetCode炒股习题案例分析

## 一、动态规划与算法交易概述

动态规划(Dynamic Programming, DP)作为算法设计中的核心思想，在解决最优化问题中展现出独特优势。其通过将复杂问题分解为重叠子问题，并存储中间结果避免重复计算，显著提升算法效率。

在量化交易领域，DP算法尤其适用于解决具有时间序列特性的金融决策问题。股票交易作为典型的序列决策问题，其"买入-卖出"决策过程天然符合DP的问题特征：

1. **多阶段决策**：每个交易日代表一个决策阶段
2. **状态转移**：持仓状态随操作变化
3. **最优子结构**：最终收益取决于子问题的最优解

LeetCode平台收录的股票交易系列题目（如121、122、123、188、309题等）构成了绝佳的DP算法训练场。本文将以C语言实现为核心，深入解析这些经典问题的DP解法。

## 二、基础问题：单次交易（LeetCode 121）

### 问题描述
给定数组`prices`，其中`prices[i]`表示第i天股票价格。限制最多完成一笔交易（买入并卖出），求最大利润。

### 暴力解法分析
```c
int maxProfit(int* prices, int pricesSize) {
    int max = 0;
    for(int i = 0; i < pricesSize; i++) {
        for(int j = i + 1; j < pricesSize; j++) {
            int profit = prices[j] - prices[i];
            if(profit > max) max = profit;
        }
    }
    return max;
}

时间复杂度O(n²)，空间复杂度O(1)，效率低下。

DP状态定义

定义状态dp[i]表示前i天的最低价格：

dp[i] = min(dp[i-1], prices[i])

优化解法实现

int maxProfit(int* prices, int pricesSize) {
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for(int i = 1; i < pricesSize; i++) {
        if(prices[i] < minPrice) {
            minPrice = prices[i];
        } else if(prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }
    return maxProfit;
}

时间复杂度O(n)，空间复杂度O(1)。

三、无限交易问题（LeetCode 122）

问题升级

允许进行多次交易，但必须完成前一次交易后才能开始下一次。

贪心算法解法

int maxProfit(int* prices, int pricesSize) {
    int profit = 0;
    for(int i = 1; i < pricesSize; i++) {
        if(prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

DP状态机分析

定义两种状态： - dp[i][0]：第i天不持有股票的最大利润 - dp[i][1]：第i天持有股票的最大利润

状态转移方程：

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])

C语言实现

int maxProfit(int* prices, int pricesSize) {
    int dp0 = 0, dp1 = -prices[0];
    for(int i = 1; i < pricesSize; i++) {
        int new_dp0 = fmax(dp0, dp1 + prices[i]);
        int new_dp1 = fmax(dp1, dp0 - prices[i]);
        dp0 = new_dp0;
        dp1 = new_dp1;
    }
    return dp0;
}

四、含冷却期的交易（LeetCode 309）

问题复杂化

卖出股票后需要等待一天才能再次买入。

三维状态定义

引入冷却状态： - dp[i][0]：持有股票 - dp[i][1]：不持有且处于冷却 - dp[i][2]：不持有且非冷却

状态转移方程

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

内存优化实现

int maxProfit(int* prices, int pricesSize) {
    if(pricesSize == 0) return 0;
    
    int hold = -prices[0];
    int coolDown = 0;
    int noHold = 0;
    
    for(int i = 1; i < pricesSize; i++) {
        int newHold = fmax(hold, noHold - prices[i]);
        int newCoolDown = hold + prices[i];
        int newNoHold = fmax(noHold, coolDown);
        
        hold = newHold;
        coolDown = newCoolDown;
        noHold = newNoHold;
    }
    return fmax(coolDown, noHold);
}

五、交易次数限制问题（LeetCode 188）

问题核心

最多完成k次交易时的最大利润。

三维DP构建

定义状态dp[i][k][s]： - i：天数 - k：剩余交易次数 - s：持仓状态（0/1）

状态转移方程

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

C语言优化实现

int maxProfit(int k, int* prices, int pricesSize) {
    if(pricesSize == 0) return 0;
    
    if(k >= pricesSize / 2) {
        // 转换为无限交易问题
        int profit = 0;
        for(int i = 1; i < pricesSize; i++) {
            if(prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
    
    int* buy = (int*)malloc((k+1) * sizeof(int));
    int* sell = (int*)malloc((k+1) * sizeof(int));
    
    for(int i = 0; i <= k; i++) {
        buy[i] = -prices[0];
        sell[i] = 0;
    }
    
    for(int i = 1; i < pricesSize; i++) {
        for(int j = 1; j <= k; j++) {
            buy[j] = fmax(buy[j], sell[j-1] - prices[i]);
            sell[j] = fmax(sell[j], buy[j] + prices[i]);
        }
    }
    
    int result = sell[k];
    free(buy);
    free(sell);
    return result;
}

六、算法性能对比分析

七、调试技巧与常见错误

1. 边界条件处理：

   if(pricesSize == 0 || k == 0) return 0;
   

2. 整数溢出防护：

   if(profit > INT_MAX - prices[i]) {
      // 异常处理
   }
   

3. DP数组初始化：

   dp[0][0] = 0;           // 第一天不买
   dp[0][1] = -prices[0];  // 第一天买入
   

4. 内存泄漏检查：

   free(dp);  // 多维数组需逐层释放
   

八、扩展思考

1. 空间优化范式：

   // 原始版本
   int dp[pricesSize][2];
   // 优化版本
   int dp0, dp1; 
   

2. 泛化状态转移方程：

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

3. 实际交易系统适配：

   • 加入交易手续费因素
   • 考虑滑点影响
   • 处理分钟级高频数据

九、总结

通过本系列LeetCode股票问题的DP解法分析，我们可以提炼出以下核心经验：

1. 状态定义优先：明确每个状态的实际含义
2. 维度逐步升级：从单次交易到多次交易再到冷却期
3. 空间复杂度优化：滚动数组或变量替换技巧
4. C语言实现要点：
   • 指针操作的高效利用
   • 动态内存的精确控制
   • 数学函数的正确调用（如fmax）

股票交易问题作为DP算法的经典应用场景，其解题思路可延伸至其他序列决策问题，如资源调度、路径规划等。建议读者在理解本文案例的基础上，尝试解决LeetCode上的其他变种问题（如714题含手续费情况），以深化对DP算法的掌握。

“算法交易的本质是将市场机会转化为状态转移方程” —— 量化交易箴言 “`