423 线性DP 股票买卖K笔交易【动态规划】
// 空间优化
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010, M = 110;
int w[N], f[M][2];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int j = 0; j <= k; j++) f[j][1] = -1e6;
for (int i = 1; i <= n ; i++)
for (int j = 1; j <= k ; j++) {
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);
f[j][0] = max(f[j][0], f[j][1] + w[i]);
}
cout << f[k][0];
}
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010, M = 110;
int w[N], f[N][M][2];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int j = 0; j <= k; j++) f[0][j][1] = -1e6;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++) {
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
}
cout << f[n][k][0];
}//三维保证正确
j++ 正序,先更新f[j][0]再更新f[j][1]
for (int j = 1; j <= k ; j++) {
f[j][0] = max(f[j][0], f[j][1] + w[i]);
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);\\交换顺序也是正确
f[j][0] = max(f[j][0], f[j][1] + w[i]); f[j][0]相当于f[i-1][j][0],f[j][1] + w[i]相当于f[i-1][j][1] + w[i]
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);// 原代码
f[j][0] = max(f[i-1][j][0], f[i-1][j][1] + w[i]);// 实际代码与原代码等价
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1]相当于f[i-1][j][1],f[j - 1][0] - w[i]相当于f[i][j - 1][0] - w[i]
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);原代码
f[i][j][1] = max(f[i - 1][j][1], f[i][j - 1][0] - w[i]);滚动数组等价代码,滚动数组的更新有些数偏大
f[i][j - 1][0] - w[i]必然大于等于f[i - 1][j - 1][0] - w[i]
f[j][0]更新正确,f[j][1]更新错误
j++ 正序,先更新f[j][1]再更新f[j][0]
for (int j = 1; j <= k ; j++) {
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);\\交换顺序也是正确
f[j][0] = max(f[j][0], f[j][1] + w[i]);
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1];f[j][1]存的是旧值f[i - 1][j][1], f[j - 1][0] - w[i] 存储f[i][j - 1][0] - w[i];
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);//原代码
f[j][1] = max(f[i - 1][j][1],f[i][j - 1][0] - w[i]) //滚动数组某些值必然偏大更新
f[j][0] = max(f[j][0], f[j][1] + w[i]); f[j][1]相当于f[i-1][j][0],f[j][1] + w[i]相当于 max(f[i - 1][j][1]+w[i],f[i][j - 1][0])
f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1] + w[i]); // 原代码
f[j][0] = max( f[i-1][j][0], f[i-1][j][1]+w[i],f[i][j - 1][0])// 按理说大于等于原代码才行
多了个这玩意f[i][j - 1][0]
f[i][j][0] 前i天,交易了j笔,手头无票 肯定大于 前i天,交易了j-1笔,手头无票
max(f[i-1][j][0], f[i-1][j][1]+w[i])>= f[i][j - 1][0]
f[j][1]更新错误,f[j][0]更新正确
如果这个可行,就保证了正确性f[j][0]
是什么保证了滚动数组的正确性,不光是正序还是逆序,更新位置交换也一样
j-- 逆序,先更新f[j][0]再更新f[j][1]
for (int j = k; j >=1 ; j--) {
f[j][0] = max(f[j][0], f[j][1] + w[i]);
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);
}
f[j][0] = max(f[j][0], f[j][1] + w[i]); f[j][0]存的是旧值f[i - 1][j][0],f[j][1] + w[i]存的是f[i-1][j][1] + w[i]
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]); //原代码
f[j][0] = max(f[i - 1][j][0], f[i-1][j][1] + w[i]);实际代码与原代码等价
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1]存的是旧值f[i-1][j][1],f[j - 1][0] - w[i] 存的是 f[i-1][j - 1][0] - w[i]
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);// 原代码
f[j][1] = max(f[i-1][j][1], f[i-1][j - 1][0] - w[i])// 实际代码与原代码等价
f[j][0]、f[j][1]都更新正确
j-- 逆序,先更新f[j][1]再更新f[j][0]
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);
f[j][0] = max(f[j][0], f[j][1] + w[i]);
f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1]存的是旧值f[i-1][j][1],f[j - 1][0] - w[i] 存的是 f[i-1][j - 1][0] - w[i]
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);// 原代码
f[j][1] = max(f[i-1][j][1], f[i-1][j - 1][0] - w[i])// 实际代码与原代码等价
f[j][0] = max(f[j][0], f[j][1] + w[i]);f[j][0]存的是旧值f[i - 1][j][0],f[j][1] + w[i]存的是max(f[i-1][j][1]+ w[i], f[i-1][j - 1][0])
f[j][0] = max(f[i - 1][j][0], f[i-1][j][1]+ w[i], f[i-1][j - 1][0]);
更新f[j][0]就是更新f[i][j][0] ,也是多了一个这玩意 f[i-1][j - 1][0] , max(f[i - 1][j][0], f[i-1][j][1]+ w[i])>= f[i-1][j - 1][0]
f[j][1]正确,f[j][0]正确
