电商网站价格监控,网站开发游戏程序开发,陕西有限公司网站建设招标公告,网络信息有限公司第九章 动态规划part11 123.买卖股票的最佳时机III // 版本一
class Solution {public int maxProfit(int[] prices) {int len prices.length;// 边界判断, 题目中 length 1, 所以可省去if (prices.length 0) return 0;/** 定义 5 种状态:* 0: 没有操作, 1: 第一次买入… 第九章 动态规划part11 123.买卖股票的最佳时机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[len][5];dp[0][1] -prices[0];// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润dp[0][3] -prices[0];for (int i 1; i len; i) {dp[i][1] Math.max(dp[i - 1][1], -prices[i]);dp[i][2] Math.max(dp[i - 1][2], dp[i - 1][1] prices[i]);dp[i][3] Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] Math.max(dp[i - 1][4], dp[i - 1][3] prices[i]);}return dp[len - 1][4];}
} 思路于上两个股票买卖问题的区别在于这道题限制了买卖次数需要定义五种状态0、1、2、3、4来代表不同的状态。然后使用递推公式对dp数组进行更新。 188.买卖股票的最佳时机IV // 版本一: 三维 dp数组
class Solution {public int maxProfit(int k, int[] prices) {if (prices.length 0) return 0;// [天数][交易次数][是否持有股票]int len prices.length;int[][][] dp new int[len][k 1][2];// dp数组初始化// 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润for (int i 0; i k; i) {dp[0][i][1] -prices[0];}for (int i 1; i len; i) {for (int j 1; j k; j) {// dp方程, 0表示不持有/卖出, 1表示持有/买入dp[i][j][0] Math.max(dp[i - 1][j][0], dp[i - 1][j][1] prices[i]);dp[i][j][1] Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);}}return dp[len - 1][k][0];}
}// 版本二: 二维 dp数组
class Solution {public int maxProfit(int k, int[] prices) {if (prices.length 0) return 0;// [天数][股票状态]// 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作int len prices.length;int[][] dp new int[len][k*2 1];// dp数组的初始化, 与版本一同理for (int i 1; i k*2; i 2) {dp[0][i] -prices[0];}for (int i 1; i len; i) {for (int j 0; j k*2 - 1; j 2) {dp[i][j 1] Math.max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]);dp[i][j 2] Math.max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]);}}return dp[len - 1][k*2];}
} 思路该题与上题的区别在于该题是至多能k次所以二维数组需要2*k1的维度1、3、5等奇数代表持有股票2、4、6等偶数代表不持有股票。然后根据递推公式进行遍历递推。再进行dp数组的初始化。
