动态规划解股票最大利润与斐波那契数列问题

"Day08_剑指Offer.md" 在给定的代码中，我们有两个Java程序，分别解决两个不同的问题。第一个问题是寻找股票的最大利润，第二个问题是计算青蛙跳上n级台阶的不同方法数，这个问题与斐波那契数列有关。 ### 股票最大利润问题 这是经典的动态规划问题，目标是从给定的一系列股票价格中找到一次买卖操作所能获得的最大利润。代码中的`MaxProfit`类实现了解决方案。 **核心算法**： 1. 定义两个变量，`cost`表示最低价格，初始化为正无穷大；`profit`表示当前最大利润，初始化为0。 2. 遍历价格数组，对于每个价格`price`： - 更新`cost`为当前价格和已知最低价格中的较小值，确保我们始终知道最低价格。 - 计算当天卖出的利润`price - cost`，并用这个利润更新`profit`，取两者中的较大值。这样可以确保我们始终跟踪到目前为止的最大利润。 3. 返回`profit`作为结果。 **示例**： 给定价格数组`[7, 1, 5, 3, 6, 4]`，在第2天买入（价格1），在第5天卖出（价格6），可以获得最大利润5（6-1）。 ### 青蛙跳台阶问题 第二个问题是一个与斐波那契数列相关的动态规划问题。`NumWays`类提供了计算解决方案的方法。 **核心算法**： 1. 初始化两个变量`a`和`b`，分别代表前两个斐波那契数，这里设为1（F(0) = F(1) = 1）。 2. 使用一个循环，从第2个台阶开始迭代到n，每次迭代： - 计算当前台阶的跳法总数`sum`，即前两个斐波那契数之和，同时对结果取模`1e9 + 7`以避免整数溢出。 - 更新`a`和`b`，使得`a`变为原来的`b`，`b`变为`sum`。 3. 返回`a`作为结果，它代表了第n个台阶的跳法总数。 **斐波那契数列**： 斐波那契数列F(n)定义如下： - F(0) = 1 - F(1) = 1 - F(n) = F(n-1) + F(n-2)，对于n > 1 在这个问题中，起始的两个斐波那契数都是1（F(0)和F(1)），然后通过迭代计算后续的斐波那契数。 这两个问题都体现了动态规划的思想，即通过将大问题分解为更小的子问题，并利用子问题的解来构建原问题的解，避免了重复计算，提高了效率。在股票问题中，动态规划体现在逐个处理价格并更新最大利润；在青蛙问题中，动态规划体现在逐步计算斐波那契数列的项。