leetcode地址: https://leetcode.com/problems...
我对这个算法慢慢的还是可以想通的, 但是为什么他是动态规划呢? 动态规划不是要话分子问题, 列出递推方程的吗?但是这个题并不能列出递推方程的...还是说我思考的方式不对. 望指点一下这个算法的思想
public class BestTimeToBuyAndSellStockIII
{
public int maxProfit(int[] prices)
{
if(prices.length == 0) return 0;
int ans = 0;
int n = prices.length;
//正向遍历,opt[i]表示 prices[0...i]内做一次交易的最大收益.
int opt[] = new int[n];
opt[0] = 0;
int low = prices[0];
int curAns = 0;
for(int i = 1; i < n; i++)
{
if(prices[i] < low)
low = prices[i];
else if(curAns < prices[i] - low)
curAns = prices[i] - low;
opt[i] = curAns;
}
//逆向遍历, opt[i]表示 prices[i...n-1]内做一次交易的最大收益.
int optReverse[] = new int[n];
optReverse[n - 1] = 0;
curAns = 0;
int high = prices[n - 1];
for(int i = n - 2; i >= 0; i--)
{
if(prices[i] > high) high = prices[i];
else if(curAns < high - prices[i]) curAns = high - prices[i];
optReverse[i] = curAns;
}
//再进行划分,分别计算两个部分
for(int i = 0; i < n; i++)
{
int tmp = opt[i] + optReverse[i];
if(ans < tmp) ans = tmp;
}
return ans;
}
}
天蓬老师2017-04-18 09:47:25
이 문제는 먼저 순방향 순회와 역방향 순회라는 두 가지 문제로 분해됩니다.
이 단계는 동적 프로그래밍으로 간주되어서는 안 됩니다.
그러나 두 가지 작은 문제는 내부적으로 동적 프로그래밍 알고리즘을 사용합니다.
모든 작은 단계는 재귀적 정의입니다. 이전 K일의 최상의 거래 방법을 알고, K+1일의 가격을 더할 때 가장 좋은 거래 방법은 무엇입니까?
K는 0에서 N까지 상승한다고 알려져 있으므로 이전 N일 동안 가장 좋은 거래 방식을 구하게 됩니다.