假设你有一个数组,长度为,其中是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票
2. 如果不能获取收益,请返回0
3. 假设买入卖出均无手续费
1. 你最多可以对该股票有笔交易操作,一笔交易代表着一次买入与一次卖出,但是再次购买前必须卖出之前的股票
2. 如果不能获取收益,请返回0
3. 假设买入卖出均无手续费
数据范围:
[8,9,3,5,1,3],3
5
第一天(股票价格=8)买进,第二天(股票价格=9)卖出,收益为1第三天(股票价格=3)买进,第四天(股票价格=5)卖出,收益为2第五天(股票价格=1)买进,第六天(股票价格=3)卖出,收益为2总收益为5。
[3,2,5,0,0,3,1,4],2
7
第二天(股票价格=2)买进,第三天(股票价格=5)卖出,收益为3第五天(股票价格=0)买进,第八天(股票价格=4)卖出,收益为4总收益为7
[9,8,4,1],4
0
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param k int整型 * @return int整型 */ int maximumProfit = 0; public int maxProfit (int[] prices, int k) { // write code here recurrent(prices, 0, k, 0, true); return maximumProfit; } private void recurrent(int[] prices, int day, int rest, int profit, boolean notBuy) { if(day == prices.length || rest == 0){ // 来到最后一天或交易数已经用完,结算收益 maximumProfit = Math.max(maximumProfit, profit); return; } if(notBuy){ // 还没买过可以买或者不买 recurrent(prices, day + 1, rest, profit, notBuy); // 不买 recurrent(prices, day + 1, rest, profit - prices[day], !notBuy); // 买 }else{ // 当前可以选择卖与不卖 recurrent(prices, day + 1, rest, profit, notBuy); // 不卖 recurrent(prices, day + 1, rest - 1, profit + prices[day], !notBuy); // 卖 } } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param k int整型 * @return int整型 */ public int maxProfit (int[] prices, int k) { // write code here int n = prices.length; if(n == 0) return 0; int[][][] dp = new int[k + 1][n][2]; for(int i = 0; i <= k; i++){ dp[i][0][1] = -prices[0]; // 首日买入均为负债情况 } for(int day = 1; day < n; day++){ for(int rest = k - 1; rest >= 0; rest--){ // 要保证第day天手上无股票,可以在前一天持股的基础上卖掉也可以直接从前一天无股的状态转移过来 dp[rest][day][0] = Math.max(dp[rest][day - 1][0], dp[rest][day - 1][1] + prices[day]); // 要保证第day天手上有股票,可以在前一天无股的基础上买入也可以直接从前一天有股的状态转移过来 dp[rest][day][1] = Math.max(dp[rest][day - 1][1], dp[rest + 1][day - 1][0] - prices[day]); // 开启一次新的交易会使得剩余交易数减1 } } return dp[0][n - 1][0]; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param k int整型 * @return int整型 */ public int maxProfit (int[] prices, int k) { // write code here int n = prices.length; if(n == 0) return 0; int[][] dp = new int[k + 1][2]; for(int i = 0; i <= k; i++){ dp[i][1] = -prices[0]; // 首日买入均为负债情况 } for(int day = 1; day < n; day++){ for(int rest = k - 1; rest >= 0; rest--){ // 要保证第day天手上无股票,可以在前一天持股的基础上卖掉也可以直接从前一天无股的状态转移过来 dp[rest][0] = Math.max(dp[rest][0], dp[rest][1] + prices[day]); // 要保证第day天手上有股票,可以在前一天无股的基础上买入也可以直接从前一天有股的状态转移过来 dp[rest][1] = Math.max(dp[rest][1], dp[rest + 1][0] - prices[day]); } } // 返回剩余交易数为0,且手中已经没有股票时的利润 return dp[0][0]; } }听过左神讲的从暴力递归到动态规划的解题思路,再经过一定量题目的积累,越来越感觉对动态规划的题目而言,重中之重应该是找到尝试的方案,然后不断优化整个算法过程(暴力递归->记忆化搜索->动态规划->斜率优化或空间压缩的动态规划),这样是最稳妥的。因为对于一道没有见过的新题而言,短时间内定义出对解题有帮助的状态,并找出状态转移方程是十分困难的。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型vector * @param k int整型 * @return int整型 */ int maxProfit(vector<int>& prices, int k) { // write code here //2k+1个状态 0是无操作 奇数1,3..是买入 偶数2,4...是卖出 if(prices.size()==0)return 0; vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0)); //买入转态的初始化 for(int j=1;j<2*k;j+=2){ dp[0][j] =-prices[0]; } for(int i=1;i<prices.size();i++){ for(int j=0;j<2*k-1;j+=2){ //买入操作 保持上一次的买入操作 或者 上次是卖出此次买入 dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]); //卖出操作 保持上一次的卖出操作 或者 上次是买入操作此次卖出 dp[i][j+2] =max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]); } } return dp[prices.size()-1][2*k]; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param k int整型 * @return int整型 */ public static int maxProfit(int[] prices, int k) { if (prices == null || prices.length == 0) return 0; int n = prices.length; if (k >= n / 2) { // 如果k大于等于n/2,问题退化为不限交易次数 return maxProfitUnlimited(prices); } int[][] dp = new int[n][k + 1]; // 限制购买次数, j 表示购买了多少次 for (int j = 1; j <= k; j++) { // 当首次购买时,利润为负值 int maxBefore = -prices[0]; for (int i = 1; i < n; i++) { // 关键一步,状态转移方程, 完成了 j 次交易, 但第 i 天也不卖, if (((i + 1) & 1) == 0) /*表示卖出*/ dp[i][j] = Math.max(dp[i - 1][j], prices[i] + maxBefore); else /*表示买入*/ // dp[i-1][j-1] 表示第i-1次操作时,完成了 j-1笔交易,的利润,再减去当前的价格,因为当前可能是买入 maxBefore = Math.max(maxBefore, dp[i - 1][j - 1] - prices[i]); } } return dp[n - 1][k]; } // 不限制购买次数,只要有利润,就加上 private static int maxProfitUnlimited(int[] prices) { int profit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i - 1]; } } return profit; } }要解决这个问题,我们可以运用动态规划的思想来求解。具体地,我们将使用二维动态规划数组 `dp` 来记录每一步的最大收益。`dp[i][j]` 表示前 `i` 天完成最多 `j` 笔交易所能获得的最大利润。