本文共 877 字，大约阅读时间需要 2 分钟。
O(N^3) dp通用解法，会超时：
很多类似区间dp可以采用这个模版。int maxProfit(int k, vector & prices) { int N = prices.size(); int K = min(k,N/2); int mx[N+1][N+1]; int mn[N+1][N+1]; int one[N+1][N+1]; int dp[K+1][N+1]; memset(mx,0,sizeof(mx)); memset(mn,0,sizeof(mn)); memset(one,0,sizeof(one)); memset(dp,0,sizeof(dp)); for(int i=0;i =0;i--){ for(int j=i+1;j =0;l--){ for(int r=l;r 对于股票比较特殊，有特殊处理方法：
初始手里面价格为0，
当买入时，相当于花费prices价格， 卖出时，相当于挣得prices价格。 这样处理的好处是状态可以叠加。 处于一个股票点时，后面股票走势的收益是固定的。 所以，当前股票点价格最高，那么最后得到的结果也是最优的。 所以，一道看似区间dp，实际上只是一道普通dp。如果只能买卖一次，只需要维护一个值，来代表手中的最大价格。
遍历每个股票点，最后得到的就是利润。如果可以买卖k次，只需要维护k个值，来代表k次交易后手中最大价格。
int maxProfit(int k, vector & prices) { int n = prices.size(); k = min(k,n/2); int f[k+1],g[k+1]; memset(f,0,sizeof(f)); memset(g,0xc0,sizeof(g)); for(int i=0;i 转载地址：http://wiwji.baihongyu.com/