m********7
发帖数: 1368 | 1 大家新年好~！
leetcode上 stock III的这个 dp 解法，http://www.cnblogs.com/caijinlong/archive/2013/05/01/3053165.html
上讲的dp算法看懂了，但是代码实现和算法如何对应起来的，没看懂。。
欢迎大牛们指导~~谢！！
code:
int maxProfit(vector &prices) {
int f[3] = {0};
int g[3] = {0};
int n = prices.size() - 1;
for (int i = 0; i < n; ++i) {
int diff = prices[i+1] - prices[i];
int m = min(i+1, 2);
for (int j = m; j >= 1; --j) {
f[j] = max(f[j], g[j-1]) + diff;
g[j] = max(g[j], f[j]);
}
}
return max(g[1], g[2]);
} | m********7
发帖数: 1368 | | A*********c
发帖数: 430 | 3 不是大牛，表达能力有限，试着解释一下。
我估计你不懂的是这两行：
12 f[j] = max(f[j], g[j-1]) + diff;
13 g[j] = max(g[j], f[j]);
你看懂了算法，就按着算法说。
该算算法的核心是这个：f[i][j] = max(g[j-1] + a[i], f[i-1][j] + a[i]).
第12行就是算这个，其中diff就是a[i].
第13行做得就是“memorize the optimal j-1segments”
算法仅仅用了常数空间的原因是因为f仅仅依赖于前一个f，而不是前面所有的f值。而g
仅仅依赖于f和当前的g。
完了。
【在 m********7 的大作中提到】
: 大家新年好~！
: leetcode上 stock III的这个 dp 解法，http://www.cnblogs.com/caijinlong/archive/2013/05/01/3053165.html
: 上讲的dp算法看懂了，但是代码实现和算法如何对应起来的，没看懂。。
: 欢迎大牛们指导~~谢！！
: code:
: int maxProfit(vector &prices) {
: int f[3] = {0};
: int g[3] = {0};
: int n = prices.size() - 1;
: for (int i = 0; i < n; ++i) {
| m********7
发帖数: 1368 | 4 Zeal,
谢谢你帮忙讲解。。
我看懂的是算法和时间复杂度O(mn),空间复杂度O(m)，怪我，不理解的地方应该先说出
来的，那我们看着代码讨论吧。。
3 int maxProfit(vector &prices) {
4 int f[3] = {0};
5 int g[3] = {0};
6
7 int n = prices.size() - 1;
8 for (int i = 0; i < n; ++i) {
9 int diff = prices[i+1] - prices[i];
10 int m = min(i+1, 2);
11 for (int j = m; j >= 1; --j) {
12 f[j] = max(f[j], g[j-1]) + diff;
13 g[j] = max(g[j], f[j]);
14 }
15 }
16 return max(g[1], g[2]);
17 }
1） 第11行，为啥要倒着算f[j] 和g[j]呢，像fibonacci/climbing stairs/robot
path一样，后面的fj依赖前面的fj-1,应该从base case开始算然后递推出后面的fj的。
如果倒着算，不是前面的f依赖后面的f了吗？
2）为啥不返回 g[j], 却是max(g[j],g[j-1])呢？ 按照定义g[j]最后保存的就是
entire array's optimal j segments结果吧。。
而g
【在 A*********c 的大作中提到】
: 不是大牛，表达能力有限，试着解释一下。
: 我估计你不懂的是这两行：
: 12 f[j] = max(f[j], g[j-1]) + diff;
: 13 g[j] = max(g[j], f[j]);
: 你看懂了算法，就按着算法说。
: 该算算法的核心是这个：f[i][j] = max(g[j-1] + a[i], f[i-1][j] + a[i]).
: 第12行就是算这个，其中diff就是a[i].
: 第13行做得就是“memorize the optimal j-1segments”
: 算法仅仅用了常数空间的原因是因为f仅仅依赖于前一个f，而不是前面所有的f值。而g
: 仅仅依赖于f和当前的g。
| H******9
发帖数: 8087 | | f******n
发帖数: 198 | 6 1. 这个code写得有点“fancy。。。” 其实第10行算出来的m最多就是2，也就是说对
于任何一个price point，最多可以做两次transaction。但是因为第一点只能做一次，
所以就写出了第10行这样的code。然后呢那个loop其实最多就运行两次，一次算two
transactions的最大值，第二次算one transaction的最大值。因为前一个要用到后一
个的值，所以要先更新前一个，再更新后一个（第12行f[j]要用到g[j - 1]）。
2. g[1]是one transaction的最优解，g[2]是two transactions的最优解，所以最后结
果是max(g[1], g[2])。如果题目允许最多3次transaction，你就会看到f和g都存4个值
，结果是max(g[1], g[2], g[3])，并且算g[3]的时候用到g[2]，算g[2]的时候用到g[1
]，所以还是倒着算的。 | b*********h
发帖数: 103 | 7 那题解和程序是我贴 Leetcode 老版 Discuss 上的，这博客里的几篇题解都是抄那里的
其实就是滚动数组优化了一下空间，DP 实现的常用技巧
倒着循环什么的是滚动数组里常用的技巧，避免一个东西重复使用，比如在 01 背包里
要倒着循环，完全背包要正着循环
其实 int f[2], g[2] 就够了，只不过这样写起来会稍微猥琐一点 | m********7
发帖数: 1368 | 8 这个是我想要的解答，长见识了。。谢谢大牛！请接纳包子~~ ^^
里的
【在 b*********h 的大作中提到】
: 那题解和程序是我贴 Leetcode 老版 Discuss 上的，这博客里的几篇题解都是抄那里的
: 其实就是滚动数组优化了一下空间，DP 实现的常用技巧
: 倒着循环什么的是滚动数组里常用的技巧，避免一个东西重复使用，比如在 01 背包里
: 要倒着循环，完全背包要正着循环
: 其实 int f[2], g[2] 就够了，只不过这样写起来会稍微猥琐一点
|
|
