一、算法思维的本质：从 “暴力” 到 “聪明” 的进化​

在编程解决实际问题时，我们总会面临 “如何更高效找到答案” 的抉择。比如股市投资中 “何时买入卖出获利最大”，最直接的想法是枚举所有可能，但当数据规模扩大，暴力枚举会瞬间失效。这时候，动态规划和贪心算法就成了我们的 “优化利器”—— 它们本质都是 “通过合理的决策逻辑，减少无效计算”，但思路却截然不同。

二、动态规划：“拆分问题 + 记忆答案” 的智慧​

1. 动态规划的核心思想​

动态规划的核心是 “将复杂问题拆分为重叠子问题，通过记忆子问题的解，避免重复计算”。它就像解拼图：把大拼图拆成小碎片，解决每个碎片后，组合起来就是完整答案，而且不会重复拼同一碎片。​

2. C++ 实现动态规划的关键步骤​

（1）定义状态：明确 dp [i] 或 dp [i][j] 代表的含义（比如 “前 i 天的最大利润”）；​

（2）寻找状态转移方程：确定 dp [i] 与 dp [i-1] 等前序状态的关系（核心难点）；​

（3）初始化边界：设置初始状态（比如 dp [0] = 0，无交易时利润为 0）；​

（4）递推计算：从边界开始，逐步推导到目标状态。

三、贪心算法：“局部最优” 能否通向 “全局最优”？​

1. 贪心算法的核心思想​

贪心算法（Greedy Algorithm）的逻辑更直接：每一步都做出当前看起来最优的选择，期望最终得到全局最优解。它就像下山时 “每次都走最陡的路”，不考虑后续路径，只关注当下的最优决策。​

2. 贪心与动态规划的本质区别​

​

特性​	动态规划​	贪心算法​
决策逻辑​	考虑所有前序状态，全局最优​	只选当前最优，局部最优​
子问题关系​	子问题重叠，需记忆​	子问题独立，无需记忆​
适用场景​	最优子结构 + 重叠子问题​	贪心选择性质 + 最优子结构​

四、实战：枚举实现股市投资的 “低买高卖”​

1. 问题定义​

假设已知未来 N 天的股票价格，允许 “最多买卖一次”（买入后必须卖出），求最大利润。如果所有天数价格递减，则利润为 0（不交易）。​

2. 枚举实现：暴力与优化​

（1）纯暴力枚举（O (n²)）​

最直接的思路：枚举所有 “买入日 i” 和 “卖出日 j（j > i）”，计算利润 prices [j] - prices [i]，取最大值。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
// 暴力枚举法求解股市单次投资最大收益：遍历所有买入-卖出组合，找到最佳买卖点及最大收益
void findBestTrade_BruteForce(vector<int>& prices, int& buyDay, int& sellDay, int& maxProfit) {
    int n = prices.size();
    if (n < 2) { // 若天数不足2天，无法完成“买入后卖出”的交易
        maxProfit = 0;
        buyDay = sellDay = -1;
        return;
    }
    maxProfit = 0;    // 初始化最大收益为0
    buyDay = 0;       // 初始化买入日期（索引）
    sellDay = 0;      // 初始化卖出日期（索引）
    // 外层循环：枚举所有可能的买入日期（i为索引，对应第i+1天）
    for (int i = 0; i < n - 1; ++i) {
        // 内层循环：枚举i之后的所有卖出日期（j为索引，对应第j+1天）
        for (int j = i + 1; j < n; ++j) {
            int currentProfit = prices[j] - prices[i]; // 计算当前组合的收益
            // 若当前收益大于最大收益，更新结果
            if (currentProfit > maxProfit) {
                maxProfit = currentProfit;
                buyDay = i;   // 更新买入日期索引
                sellDay = j;  // 更新卖出日期索引
            }
        }
    }
}
int main() {
    srand(time(0)); // 初始化随机数生成器
    vector<int> prices(30); // 存储30天的股价
    // 随机生成30天的股价，范围为1到100，同时输出每天股价
    cout << "===== 30天股票价格 =====\n";
    for (int i = 0; i < 30; ++i) {
        prices[i] = rand() % 100 + 1;
        cout << "第" << i + 1 << "天股价：" << prices[i] << endl;
    }
    int buyDay, sellDay, maxProfit;
    findBestTrade_BruteForce(prices, buyDay, sellDay, maxProfit);
    cout << "\n===== 最佳交易决策 =====\n";
    if (maxProfit > 0) {
        cout << "最佳买入时间：第" << buyDay + 1 << "天，股价" << prices[buyDay] << endl;
        cout << "最佳卖出时间：第" << sellDay + 1 << "天，股价" << prices[sellDay] << endl;
        cout << "最大收益：" << maxProfit << endl;
    } else {
        cout << "所有交易都无收益，建议不交易！" << endl;
    }
    return 0;
}

（2）优化枚举（O (n)）：贪心思想的应用​

纯暴力会重复计算很多无效差值，我们可以优化：遍历过程中记录 “当前最低买入价”，同时计算 “当前价格与最低买入价的利润”，实时更新最大利润。这本质是贪心 —— 每一步都抓住 “当前最优买入时机”。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
// 贪心算法求解股市单次投资最大收益：找到最佳买入、卖出点及最大收益
void findBestTrade(vector<int>& prices, int& buyDay, int& sellDay, int& maxProfit) {
    int n = prices.size();
    if (n < 2) { // 若天数不足2天，无法完成“买入后卖出”的交易
        maxProfit = 0;
        buyDay = sellDay = -1;
        return;
    }
    maxProfit = 0;    // 初始化最大收益为0
    buyDay = 0;       // 初始化买入日期为第1天
    sellDay = 0;      // 初始化卖出日期为第1天
    int minPriceDay = 0; // 记录“当前遍历过的最低股价的日期”，作为候选买入点
    // 从第2天开始遍历（索引为1）
    for (int i = 1; i < n; ++i) {
        // 若当前天的股价比“历史最低股价”还低，更新最低股价的日期
        if (prices[i] < prices[minPriceDay]) {
            minPriceDay = i;
        }
        // 计算“当前天股价 - 历史最低股价”的收益，若大于当前最大收益，则更新结果
        int currentProfit = prices[i] - prices[minPriceDay];
        if (currentProfit > maxProfit) {
            maxProfit = currentProfit;
            buyDay = minPriceDay;   // 买入点更新为历史最低股价的日期
            sellDay = i;            // 卖出点更新为当前天
        }
    }
}
int main() {
    srand(time(0)); // 初始化随机数生成器
    vector<int> prices(30); // 存储30天的股价
    // 随机生成30天的股价，范围为1到100
    for (int i = 0; i < 30; ++i) {
        prices[i] = rand() % 100 + 1;
        cout << "第" << i + 1 << "天股价：" << prices[i] << endl;
    }
    int buyDay, sellDay, maxProfit;
    findBestTrade(prices, buyDay, sellDay, maxProfit);
    cout << "\n===== 最佳交易决策 =====\n";
    cout << "最佳买入时间：第" << buyDay + 1 << "天，股价" << prices[buyDay] << endl;
    cout << "最佳卖出时间：第" << sellDay + 1 << "天，股价" << prices[sellDay] << endl;
    cout << "最大收益：" << maxProfit << endl;
    return 0;
}

（3）动态规划实现（O (n)）​

如果问题扩展为 “允许买卖 k 次”，贪心就失效了，此时需要动态规划。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

int maxProfitDP(const vector<int>& prices, int& buyDay, int& sellDay) {
    int n = prices.size();
    if (n < 2) {
        buyDay = sellDay = -1;
        return 0;
    }
    
    // DP状态定义
    // dp[i] 表示前i天的最大收益
    vector<int> dp(n, 0);
    
    // 记录前i天的最低股价
    vector<int> minPrice(n, 0);
    minPrice[0] = prices[0];
    
    // 记录达到最大收益时的买入和卖出日期
    vector<int> buy(n, 0);  // 前i天最大收益对应的买入日
    vector<int> sell(n, 0); // 前i天最大收益对应的卖出日
    
    // 初始化
    buyDay = sellDay = 0;
    int maxProfit = 0;
    
    // 动态规划过程 
    for (int i = 1; i < n; i++) {
        // 更新前i天的最低股价
        minPrice[i] = min(minPrice[i-1], prices[i]);
        
        // 状态转移方程：
        // dp[i] = max(dp[i-1], prices[i] - minPrice[i-1])
        int profitIfSellToday = prices[i] - minPrice[i-1];
        
        if (profitIfSellToday > dp[i-1]) {
            dp[i] = profitIfSellToday;
            // 找到minPrice[i-1]对应的日期
            for (int j = 0; j < i; j++) {
                if (prices[j] == minPrice[i-1]) {
                    buy[i] = j;
                    break;
                }
            }
            sell[i] = i;
        } else {
            dp[i] = dp[i-1];
            buy[i] = buy[i-1];
            sell[i] = sell[i-1];
        }
        
        // 更新全局最优解
        if (dp[i] > maxProfit) {
            maxProfit = dp[i];
            buyDay = buy[i];
            sellDay = sell[i];
        }
    }
    
    return maxProfit;
}
int main() {
    // 随机生成30天的股价（范围：10~200）
    srand(time(0));
    vector<int> prices;
    for (int i = 0; i < 30; ++i) {
        prices.push_back(rand() % 191 + 10); // 10~200的随机数
    }

    // 输出30天的股价
    cout << "===== 未来30天的股票价格 =====" << endl;
    for (int i = 0; i < 30; ++i) {
        cout << "第" << (i + 1) << "天：" << prices[i] << endl;
    }

    // 调用动态规划函数计算结果
    int buyDay, sellDay;
    int profit = maxProfitDP(prices, buyDay, sellDay);

    // 输出结果
    cout << "\n===== 动态规划解法 =====" << endl;
    if (profit > 0) {
        cout << "最佳买入时间：第" << (buyDay + 1) << "天，股价：" << prices[buyDay] << endl;
        cout << "最佳卖出时间：第" << (sellDay + 1) << "天，股价：" << prices[sellDay] << endl;
        cout << "最大收益：" << profit << endl;
    } else {
        cout << "未来30天无盈利机会（任何买入卖出都无法赚钱）" << endl;
    }
    
    

    return 0;
}

五、算法选择的思考：没有最好，只有最合适​

1. 枚举：适用于数据规模小、问题简单的场景，优点是逻辑直观，缺点是效率低；​
2. 贪心：适用于 “局部最优可推导全局最优” 的问题，代码简洁、效率高，但适用范围有限；​
3. 动态规划：适用于复杂的多阶段决策问题（如多笔交易、带约束条件），能保证全局最优，但代码复杂度和空间消耗更高。​

回到股市投资问题：​

（1）最多买卖 1 次：枚举、贪心即可，简单高效；​

（2）最多买卖 k 次：必须用动态规划；​

（3）可以无限次买卖：贪心或动态规划均可。​

六、总结​

算法的魅力在于 “用逻辑替代暴力”。动态规划教会我们 “拆分问题、记忆答案”，贪心算法教会我们 “抓住当下最优”，而枚举则是所有算法的基础 —— 理解它们的本质，才能在实际问题中灵活选择。​​