其实有没有冷冻期都一样,只是拉开了转移方程的间距
朴素的转移方程是 f[j] = max(f[j - 1],$\displaystyle\sum^{j - 1}_{i = 0}$num[j] - num[i] + (i - 2 >= 0 ? f[i - 2] : 0));
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> f(prices.size());
for (int j = 1; j < prices.size(); j++) {
f[j] = f[j - 1];
for(int i = j - 1; i >= 0; i--) {
f[j] = max(f[j], prices[j] - prices[i] + (i - 2 >= 0 ? f[i - 2] : 0));
}
}
return f[prices.size() - 1];
}
};
然后稍微优化一下
会发现 max的比较大小上 对于第二层循环中 num[j] 其实是 常数
max((i - 2 >= 0 ? f[i - 2]: 0) - num[i]) + num[j]
就可以减少一轮遍历
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> f(prices.size());
int max_val = INT_MIN;
for (int i = 0; i < prices.size() - 1; i++) {
max_val = max(max_val,(i - 2 >= 0 ? f[i - 2] : 0) - prices[i]);
f[i + 1] = max(f[i],max_val + prices[i + 1]);
}
return f[prices.size() - 1];
}
};