总结
1. 更新动规矩阵时, 不要 push 更新, 要用 pull更新. push 更新容易让逻辑出问题, 自己卡了很久, 改用 pull 就变得很顺利了
2. acm 题, 空间至多是百万, 再网上就会超的
3. 曾做过一道题, 和这个类似. 好像是背包问题的一个变形把, 核心都是降维. 降维的过程又是一道动规题目
给定一个大小为n的数组，数组的元素a[i]代表第i天的股票价格
设计一个算法，计算在最多允许买卖k次（一买一卖记为一次）的条件下的最大收益
需要注意的是，你不能同时拥有两份股票。也就是说在下次买入前，你必须把手头上原有的股票先卖掉
思路
1. 假设 dp[i][j] 表示前 i 天, 最多允许买卖 j 次的最大收益, 那么 dp[i][j] = max{(dp[m][j-1] + price[i]-price[m+1]),price[i]-price[0]} (0<=m<i) 需要遍历 i, j, m 时间复杂度为o (n*n*k), 提交代码超时
2. 若是把 dp[i][j] 拆开来写, 那么
dp[i][j] = max {
0 - price[0] + price[i],
dp[0][j-1] - price[1] + price[i],
dp[1][j-1] - price[2] + price[i],
...
dp[i-1][j-1] - price[i] + price[i]
}
在求解 dp[i][j] 之前, dp[i-1][j-1] 已经被求出, 所以可以存储 max(dp[m][j-1]-price[m+1]), 在 dp[i][j] 需求时直接调用, 这样的话, 时间复杂度下降一维, o(n*k)
总体的思路就是上面了
3. 假设 dp2[n-1][k-1] 为所求的最终结果, 假设
dp1[i][j] = max {
0 - price[0],
dp2[0][j-1] - price[1],
dp2[1][j-1] - price[2],
...
dp2[i-1][j-1] - price[i],
}
那么 dp2[i][j] = dp1[i][j] + price[i] ---------------- a
max(dp1[i][j], dp2[i][j-1]-price[i+1]) ==> dp1[i+1][j]
所以 dp1[i][j] = max(dp1[i-1][j], dp2[i-1][j-1]-price[i]) --------------------b
a, b 是题目的状态转移方程, 剩下的也是最难的就是初始化了
4. 首先看 dp1 的, dp1[i][j] = max(dp1[i-1][j], dp2[i-1][j-1]-price[i]). 想象一个二维矩阵, dp1[i][j] 是由其上面和左上两个格子组合, 那么 dp1[i][j] 的第一行就无法通过递推的来, 只能初始化, 手动生成. 同样的道理, dp1 第一列也无法递推而得. 不过好在 dp2[0][i] 都等于 0, dp2[i][0] 相当于 [0~i] 的最大利润, 可以递推求出.
那么, 我们看第二行需要些什么.
dp1[1][1] = max(0-price[0], dp2[0][0]-price[1]) = max(dp1[0][1], dp2[0][0]-price[1])
dp1[1][2] = max(0-price[0], dp2[0][1]-price[1]) = max(dp1[0][2], dp2[0][1]-price[1])
...
dp1[1][i] = max(0-price[0], dp2[0][i-1] -price[1])= max(dp1[0][i-1], dp2[0][i]-price[1])
所以, dp1[0][i] = 0-price[0] 即可, dp1[i][0] 不需要初始化, 因为 dp2[i][0] 可以直接求出
代码
未能通过九度测试, 第 4 个案例无法通过
#include <iostream>
#include <stdio.h>
using namespace std; int dp1[][];
int dp2[][];
int prices[]; void init(int n, int k) {
for(int i = ; i < k; i ++) {// init first line
dp1[][i] = -prices[];
dp2[][i] = ;
} int global = , local = ;
for(int i = ; i < n; i ++) {// init first column
local = max(, prices[i]-prices[i-]+local);
global = max(global, local);
dp2[i][] = global;
}
} int dodp(int n, int k) {
for(int i = ; i < n; i ++) {
for(int j = ; j < k; j ++) {
dp1[i][j] = max(dp1[i-][j], dp2[i-][j-]-prices[i]);
dp2[i][j] = dp1[i][j] + prices[i];
}
}
return dp2[n-][k-];
} int main() {
freopen("testcase.txt", "r", stdin);
int n,k;
while(scanf("%d%d", &n, &k) != EOF) {
for(int i = ; i < n; i ++)
scanf("%d", prices+i); init(n, k);
int res = dodp(n, k);
cout << res << endl;
}
return ;
}