本文共 1189 字，大约阅读时间需要 3 分钟。

class Solution {//Let f[i][j] to be the maximum sum of j segments from the first i numbers, where the last element we choose is a[i]. //We have two strategies to achieve it:////1.Choosing the optimal j-1 segments from the first k numbers, and starting a new segment with a[i]://f[i][j] = f[k][j-1] + a[i], where j-1 <= k <= i-1.//let g[j-1] = max(f[k][j-1])//2.Appending a[i] to the last segment in the first i-1 numbers//f[i][j] = f[i-1][j] + a[i].public:	int getMaxProfitDP(vector
   
     &prices, int transNum)	{		vector
    
      f(transNum+1, 0);		vector
     
       g(transNum+1, 0);		for (int i = 1; i < prices.size(); ++i)		{			int diff = prices[i]-prices[i-1];			int m = min(i, transNum);//if not enough to complete transNum transactions			for (int j = m; j >= 1; --j)			{//why scan m->1, because we can not			 //let cur diff accumulate, note: g[j-1] 				f[j] = max(f[j], g[j-1])+diff;//1.g[j-1] starting a new segment and 2.f[j] Appending a[i] to the last segment				g[j] = max(g[j], f[j]);//record			}		}		int ans = 0;		for(int i = 1; i <= transNum; ++i)			ans = max(ans, g[i]);		return ans;	}	int maxProfit(vector
      
        &prices) {		return getMaxProfitDP(prices, 2);	}};
      
     
    
   

转载地址：http://yoxti.baihongyu.com/