利用淘宝联盟做网站,腾讯企业qq,什么叫网站域名,wordpress 查询122. 买卖股票的最佳时机 II 给你一个整数数组 prices #xff0c;其中 prices[i] 表示某支股票第 i 天的价格。 在每一天#xff0c;你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买#xff0c;然后在 同一天 出售。 返回 你能获得…122. 买卖股票的最佳时机 II 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。 在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。 返回 你能获得的 最大 利润 。 问题转换 贪心
只要明天比今天价格高就在今天买入明天卖出吃掉所有收益一定能达成题意要求的收益
class Solution:def maxProfit(self, prices: List[int]) - int:res 0if len(prices) 1:return resfor i in range(1, len(prices)):tmp prices[i] - prices[i - 1]res (tmp if tmp 0 else 0)return res动态规划
下面网友写的题解十分精彩从状态转移方程可以看出计算i只需i-1可以进行滚动优化 作者liweiwei1419 链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solutions/38498/tan-xin-suan-fa-by-liweiwei1419-2/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 第 1 步定义状态
状态 dp[i][j] 定义如下
dp[i][j] 表示到下标为 i 的这一天持股状态为 j 时我们手上拥有的最大现金数。
注意限定持股状态为 j 是为了方便推导状态转移方程这样的做法满足 无后效性。
其中
第一维 i 表示下标为 i 的那一天 具有前缀性质即考虑了之前天数的交易 第二维 j 表示下标为 i 的那一天是持有股票还是持有现金。这里 0 表示持有现金cash1 表示持有股票stock。
第 2 步思考状态转移方程
状态从持有现金cash开始到最后一天我们关心的状态依然是持有现金cash 每一天状态可以转移也可以不动。状态转移用下图表示 状态转移方程写在代码中
说明
由于不限制交易次数除了最后一天每一天的状态可能不变化也可能转移 写代码的时候可以不用对最后一天单独处理输出最后一天状态为 0 的时候的值即可。
第 3 步确定初始值
起始的时候
如果什么都不做dp[0][0] 0 如果持有股票当前拥有的现金数是当天股价的相反数即 dp[0][1] -prices[i]
第 4 步确定输出值
终止的时候上面也分析了输出 dp[len - 1][0]因为一定有 dp[len - 1][0] dp[len - 1][1]。
public class Solution {public int maxProfit(int[] prices) {int len prices.length;if (len 2) {return 0;}// 0持有现金// 1持有股票// 状态转移0 → 1 → 0 → 1 → 0 → 1 → 0int[][] dp new int[len][2];dp[0][0] 0;dp[0][1] -prices[0];for (int i 1; i len; i) {// 这两行调换顺序也是可以的dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] prices[i]);dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[len - 1][0];}
}复杂度分析
时间复杂度O(N)这里 N 表示股价数组的长度 空间复杂度O(N)虽然是二维数组但是第二维是常数与问题规模无关。
