代码随想录算法训练营day41｜动态规划part08
第一题：121. Best Time to Buy and Sell Stock贪心法：
class Solution {
public int maxProfit(int[] prices) {
// 找到一个最小的购入点
int low = Integer.MAX_VALUE;
// res不断更新，直到数组循环完毕
int res = 0;
for(int i = 0; i < prices.length; i++){
low = Math.min(prices, low);
res = Math.max(prices - low, res);
}
return res;
}
}
动态规划：版本一
// 解法1
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int length = prices.length;
// dp代表第i天持有股票的最大收益
// dp代表第i天不持有股票的最大收益
int[][] dp = new int;
int result = 0;
dp = -prices;
dp = 0;
for (int i = 1; i < length; i++) {
dp = Math.max(dp, -prices);
dp = Math.max(dp + prices, dp);
}
return dp;
}
}
动态规划：版本二(利用二維數組（和卡哥思路同等），下面還有利用一維滾動數組的更優化版本)
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int dp[][] = new int;
dp = - prices;
dp = 0;
for (int i = 1; i < len; i++){
dp = Math.max(dp[(i - 1) % 2], - prices);
dp = Math.max(dp[(i - 1) % 2], prices + dp[(i - 1) % 2]);
}
return dp[(len - 1) % 2];
}
}
动态规划：版本二(利用一維數組)
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int;
// 记录一次交易，一次交易有买入卖出两种状态
// 0代表持有，1代表卖出
dp = -prices;
dp = 0;
// 可以参考斐波那契问题的优化方式
// 我们从 i=1 开始遍历数组，一共有 prices.length 天，
// 所以是 i<=prices.length
for (int i = 1; i <= prices.length; i++) {
// 前一天持有；或当天买入
dp = Math.max(dp, -prices);
// 如果 dp 被更新，那么 dp 肯定会被更新为正数的 dp
// 而不是 dp+prices==0 的0，
// 所以这里使用会改变的dp也是可以的
// 当然 dp 初始值为 0 ，被更新成 0 也没影响
// 前一天卖出；或当天卖出, 当天要卖出，得前一天持有才行
dp = Math.max(dp, dp + prices);
}
return dp;
}
} 第二题：122. Best Time to Buy and Sell Stock II
// 动态规划
class Solution
// 实现1：二维数组存储
// 可以将每天持有与否的情况分别用 dp 和 dp 来进行存储
// 时间复杂度：O(n)，空间复杂度：O(n)
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int; // 创建二维数组存储状态
dp = 0; // 初始状态
dp = -prices;
for (int i = 1; i < n; ++i) {
dp = Math.max(dp, dp + prices); // 第 i 天，没有股票
dp = Math.max(dp, dp - prices); // 第 i 天，持有股票
}
return dp; // 卖出股票收益高于持有股票收益，因此取
}
}
//DP using 2*2 Array (下方還有使用一維滾動數組的更優化版本)
class Solution {
public int maxProfit(int[] prices) {
int dp[][] = new int ;
//dp: holding the stock
//dp: not holding the stock
dp = - prices;
dp = 0;
for(int i = 1; i < prices.length; i++){
dp = Math.max(dp[(i - 1) % 2], dp[(i - 1) % 2] - prices);
dp = Math.max(dp[(i - 1) % 2], dp[(i - 1) % 2] + prices);
}
return dp[(prices.length - 1) % 2];
}
}
// 优化空间
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int;
// 0表示持有，1表示卖出
dp = -prices;
dp = 0;
for(int i = 1; i <= prices.length; i++){
// 前一天持有; 既然不限制交易次数，那么再次买股票时，要加上之前的收益
dp = Math.max(dp, dp - prices);
// 前一天卖出; 或当天卖出，当天卖出，得先持有
dp = Math.max(dp, dp + prices);
}
return dp;
}
}
第三题：123. Best Time to Buy and Sell Stock III
// 版本一
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
// 边界判断, 题目中 length >= 1, 所以可省去
if (prices.length == 0) return 0;
/*
* 定义 5 种状态:
* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
*/
int[][] dp = new int;
dp = -prices;
// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
dp = -prices;
for (int i = 1; i < len; i++) {
dp = Math.max(dp, -prices);
dp = Math.max(dp, dp + prices);
dp = Math.max(dp, dp - prices);
dp = Math.max(dp, dp + prices);
}
return dp;
}
}
// 版本二: 空间优化
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int;
// 存储两次交易的状态就行了
// dp代表第一次交易的买入
dp = -prices;
// dp代表第一次交易的卖出
dp = 0;
// dp代表第二次交易的买入
dp = -prices;
// dp代表第二次交易的卖出
dp = 0;
for(int i = 1; i <= prices.length; i++){
// 要么保持不变，要么没有就买，有了就卖
dp = Math.max(dp, -prices);
dp = Math.max(dp, dp+prices);
// 这已经是第二次交易了，所以得加上前一次交易卖出去的收获
dp = Math.max(dp, dp-prices);
dp = Math.max(dp, dp+ prices);
}
return dp;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]