网站制作商家入驻,app开发企业网站建设,免费商城系统源码,偃师网站制作Day50 动态规划 part11
123.买卖股票的最佳时机III
我的思路#xff1a; 这道题考虑了交易次数 j#xff08;最大次数为2#xff09;#xff0c;以及某天 i 应该买or卖股票#xff08;两种状态#xff09; 用三维数组表示 dp[i][j][0] – 第i天结束时#xff0c;交易j…Day50 动态规划 part11
123.买卖股票的最佳时机III
我的思路 这道题考虑了交易次数 j最大次数为2以及某天 i 应该买or卖股票两种状态 用三维数组表示 dp[i][j][0] – 第i天结束时交易j次手里没有股票 状态方程 dp[i][j][0] Math.max(dp[i - 1][j][0], dp[i - 1][j][1] prices[i]) dp[i][j][1] – 第i天结束时交易j次手里有股票 状态方程 dp[i][j][1] Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
解答
class Solution {public int maxProfit(int[] prices) {int n prices.length;int max 2;int[][][] dp new int[n][max 1][2];for(int j 0; j max; j) {dp[0][j][0] 0;dp[0][j][1] -prices[0];}for(int i 1; i n; i) {for(int j 1; j max; j) {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[n - 1][max][0];}
}188.买卖股票的最佳时机IV
我的思路: 和上一题代码一样只是这题给定了最大交易次数k只要把上一题的max换成k就行
解答
class Solution {public int maxProfit(int k, int[] prices) {int n prices.length;int[][][] dp new int[n][k 1][2];for(int j 0; j k; j) {dp[0][j][0] 0;dp[0][j][1] -prices[0];}for(int i 1; i n; i) {for(int j 1; j k; j) {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[n - 1][k][0];}
}
