算法day35-动态规划（8）
目录[*] 买卖股票的最佳时机
[*]买卖股票的最佳时机II
[*]买卖股票的最佳时机III
一、买卖股票的最佳时机
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=problem-list-v2&envId=8At1GmaZ
https://img2024.cnblogs.com/blog/2297173/202506/2297173-20250606231209747-239231664.png
[*]状态定义：
[*]使用一个二维数组 dp 表示在第 i 天持有股票时的最大收益。
[*]使用 dp 表示在第 i 天不持有股票时的最大收益。
[*]初始条件：
[*]在第 0 天，如果持有股票，最大收益是 -prices（即买入股票的花费）。
[*]在第 0 天，如果不持有股票，最大收益是 0（即没有操作）。
[*]状态转移：
[*]对于每一天 i（从 1 到 length - 1），有两种选择：
[*]持有股票：可以选择继续持有前一天的股票，或者在今天再次买入股票（此时的收益为 -prices），即 dp = Math.max(dp, -prices)。
[*]不持有股票：可以选择继续不持有前一天的股票，或者在今天卖出股票（此时的收益为 dp + prices），即 dp = Math.max(dp, dp + prices)。
[*]最终结果：
[*]在最后一天（第 length-1 天），我们关心的是不持有股票的最大收益，即 dp。
时间复杂度：
该算法的时间复杂度为 O(n)，其中 n 为股票价格数组的长度，因为只需要遍历一次数组。
空间复杂度：
该算法的空间复杂度为 O(n)，主要是由 dp 数组占用的空间决定。
class Solution { public int maxProfit(int[] prices) { //dp持有股票得到的最大收益，dp不持股最大收益 if(prices == null || prices.length == 0) return 0; int length = prices.length; int[][] dp = new int; dp = -prices; dp = 0; for(int i=1; i
页:
[1]