- 浏览: 130599 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Say you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
[balabala] 此题参照 网友博客的解法http://www.cnblogs.com/grandyang/p/4295761.html。需要维护两个dp数组,分别是local[i][j] 和global[i][j],前者表示到第i天为止至多完成j次交易且最后一笔交易于第i天完成的最大收益,是一个局部最优值,后者表示到第i天为止至多完成j次交易获取的最大值, 为全局最优值。global[i][j] = max(global[i - 1][j], local[i][j]), 这个递推式比较好理解,是按照第 i 天是否参与交易分类讨论的,local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff).
对于这个解法一度半懂不懂,为什么需要两个dp数组呢?local[][]数组的递推公式如何理解? 在理解的过程中发现可以这样去理解那些不理解的事物(说得有些绕):去掉看看效果,正确的解法里每个变量都是有其不可替换的作用的。假设我们只用一个dp数组,dp[i][j]含义同global[i][j],表示到第i天至多完成j次交易能获取的最大利润,自然地,可以按照第 i 天是否参与最后一笔交易分类讨论,于是递推公式dp[i][j] = max(dp[i - 1][j], max(dp[k][j - 1] + maxProfitBetween(k + 1, i)) ), 式中第二项表示 第i天参与交易的情况,看到仅有dp[][]数组的情况下写起来是多么复杂。于是理解了local[][]数组的好处,使算法复杂度由O(n^3)变为O(n^2)(对比Palindrome Partition II 的降维思路,目前还没看出两种降维思路的想通之处)。local[i][j]是如何递推的呢? 它的作用是记录到第 i 天至多完成 j 次交易的最大利润且第 i 天完成最后一笔交易,这最后一笔交易卖出点是day i, 买入点可以是0 - i的任意一天,分三种情况讨论:
1) 在i - 1天之前买入:这种情况下可将最后一笔交易以day[i-1]为分割点分解为两笔交易来计算,第一笔是在day[k](k < i -1)买入,day[i -1]卖出,对应于local[i - 1][j], 第二笔是day[i - 1]买入,day[i]卖出,火力为prices[i] - prices[i - 1], 于是这种情况下local[i][j] = local[i-1][j] + prices[i] - prices[i - 1]
2) 在第 i - 1天买入:local[i][j]= global[i - 1][j - 1] + prices[i] - prices[i - 1]
3) 在第 i 天买入: local[i][j]= global[i - 1][j - 1] + 0
合并起来,local[i][j] = local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff), 其中diff = prices[i] - prices[i - 1]
第三个实现yb君的思路,另一角度看问题~
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
[balabala] 此题参照 网友博客的解法http://www.cnblogs.com/grandyang/p/4295761.html。需要维护两个dp数组,分别是local[i][j] 和global[i][j],前者表示到第i天为止至多完成j次交易且最后一笔交易于第i天完成的最大收益,是一个局部最优值,后者表示到第i天为止至多完成j次交易获取的最大值, 为全局最优值。global[i][j] = max(global[i - 1][j], local[i][j]), 这个递推式比较好理解,是按照第 i 天是否参与交易分类讨论的,local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff).
对于这个解法一度半懂不懂,为什么需要两个dp数组呢?local[][]数组的递推公式如何理解? 在理解的过程中发现可以这样去理解那些不理解的事物(说得有些绕):去掉看看效果,正确的解法里每个变量都是有其不可替换的作用的。假设我们只用一个dp数组,dp[i][j]含义同global[i][j],表示到第i天至多完成j次交易能获取的最大利润,自然地,可以按照第 i 天是否参与最后一笔交易分类讨论,于是递推公式dp[i][j] = max(dp[i - 1][j], max(dp[k][j - 1] + maxProfitBetween(k + 1, i)) ), 式中第二项表示 第i天参与交易的情况,看到仅有dp[][]数组的情况下写起来是多么复杂。于是理解了local[][]数组的好处,使算法复杂度由O(n^3)变为O(n^2)(对比Palindrome Partition II 的降维思路,目前还没看出两种降维思路的想通之处)。local[i][j]是如何递推的呢? 它的作用是记录到第 i 天至多完成 j 次交易的最大利润且第 i 天完成最后一笔交易,这最后一笔交易卖出点是day i, 买入点可以是0 - i的任意一天,分三种情况讨论:
1) 在i - 1天之前买入:这种情况下可将最后一笔交易以day[i-1]为分割点分解为两笔交易来计算,第一笔是在day[k](k < i -1)买入,day[i -1]卖出,对应于local[i - 1][j], 第二笔是day[i - 1]买入,day[i]卖出,火力为prices[i] - prices[i - 1], 于是这种情况下local[i][j] = local[i-1][j] + prices[i] - prices[i - 1]
2) 在第 i - 1天买入:local[i][j]= global[i - 1][j - 1] + prices[i] - prices[i - 1]
3) 在第 i 天买入: local[i][j]= global[i - 1][j - 1] + 0
合并起来,local[i][j] = local[i][j] = max(global[i - 1][j - 1] + max(0, diff), local[i - 1][j] + diff), 其中diff = prices[i] - prices[i - 1]
第三个实现yb君的思路,另一角度看问题~
public class Solution { // Method 3: space: O(N * k), time: O(N * k) public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0) return 0; int N = prices.length; if (N <= k - 1) return maxProfitWithoutLimit(prices); int M = 2 * k; // dp[i][j]: on day i (1, 2... N), max profit after transaction j done // transaction j means buy j / 2 + j % 2 times, sell j / 2 times int[][] dp = new int[N + 1][M + 1]; for (int i = 1; i <= N; i++) { for (int j = 1; j <= i && j <= M; j++) { if (j % 2 == 1) {// buy dp[i][j] = dp[i - 1][j - 1] - prices[i - 1]; } else { // sell dp[i][j] = dp[i - 1][j - 1] + prices[i - 1]; } if (i - 1 >= j) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); } } int max = 0; for (int j = 2; j <= M; j += 2) { max = Math.max(max, dp[N][j]); } return max; } // Method 2space: O(k), time: O(N * k) public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0) return 0; int days = prices.length; if (k >= days) return maxProfit(prices); // local[j] 表示到当日至多完成j次交易,并且最后一笔交易在当日完成的最大收益 int[] local = new int[k + 1]; // global[j] 表示到当日至多完成j次交易的最大收益 int[] global = new int[k + 1]; for (int i = 1; i < days; i++) { for (int j = k; j > 0; j--) { // 逆序以利用前一天的结果 int diff = prices[i] - prices[i - 1]; local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff); global[j] = Math.max(global[j], local[j]); } } return global[k]; } // Method 1: space: O(N * k), time: O(N * k) public int maxProfit1(int k, int[] prices) { if (prices == null || prices.length == 0) return 0; int days = prices.length; if (k >= days) return maxProfit(prices); // local[i][j] 表示到第i天至多完成j次交易,并且最后一笔交易在第i天完成的最大收益 int[][] local = new int[days][k + 1]; // global[i][j] 表示到第i天至多完成j次交易的最大收益 int[][] global = new int[days][k + 1]; for (int i = 1; i < days; i++) { local[i][0] = 0; global[i][0] = 0; for (int j = 1; j <= k; j++) { int diff = prices[i] - prices[i - 1]; local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(diff, 0), local[i - 1][j] + diff); global[i][j] = Math.max(global[i - 1][j], local[i][j]); } } return global[days - 1][k]; } private int maxProfit(int[] prices) { if (prices == null || prices.length == 0) return 0; int days = prices.length; int profit = 0; int delta = 0; for (int i = 1; i < days; i++) { delta = prices[i] - prices[i - 1]; profit += delta > 0 ? delta : 0; } return profit; } }
评论
1 楼
qb_2008
2015-05-05
带进去简单例子分析一下,就知道代码为什么要这样做了。比如k = 1, prices[] = {1, 4, 3, 7}.
这个问题看成K条装配线上的N个装配站问题或许更容易理解。
N是天数,在每天你可以处于2*k+1种交易状态,让
dp[i][j]为第i天,买入j/2+j%2次,卖出j/2次的最大盈利。
dp[0][0] = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= 2 * k && j <= i; ++i) {
if (j % 2 == 1) {
// only can buy.
dp[i][j] = dp[i - 1][j - 1] - prices[i - 1];
if (i - 1 >= j) { // or keep previous value.
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
}
} else {
// only can sell.
...
}
}
}
这个问题看成K条装配线上的N个装配站问题或许更容易理解。
N是天数,在每天你可以处于2*k+1种交易状态,让
dp[i][j]为第i天,买入j/2+j%2次,卖出j/2次的最大盈利。
dp[0][0] = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= 2 * k && j <= i; ++i) {
if (j % 2 == 1) {
// only can buy.
dp[i][j] = dp[i - 1][j - 1] - prices[i - 1];
if (i - 1 >= j) { // or keep previous value.
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
}
} else {
// only can sell.
...
}
}
}
发表评论
-
Leetcode - Ugly Number II
2015-08-24 22:54 1119[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Paint House II
2015-08-20 20:37 1572There are a row of n houses, ea ... -
Leetcode - Maximum Square
2015-08-16 13:33 465Given a 2D binary matrix filled ... -
Leetcode - Paint House
2015-08-16 10:48 1114There are a row of n houses, ea ... -
Leetcode - Different Ways to Add Parentheses
2015-07-29 20:21 1154Given a string of numbers and o ... -
Jump Game II
2015-07-05 16:49 501Given an array of non-negative ... -
Leetcode - Jump Game
2015-07-05 15:52 488Given an array of non-negative ... -
Leetcode - Interleaving String
2015-06-07 11:41 566Given s1, s2, s3, find whe ... -
Leetcode - Wildcard Matching
2015-06-06 20:01 951Implement wildcard pattern ma ... -
Leetcode - Maximal Square
2015-06-04 08:25 588Given a 2D binary matrix fille ... -
Leetcode - Palindrome Partition II
2015-05-21 21:15 639Given a string s, partition ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 748Given a string s, partition s s ... -
Leetcode - House Robber II
2015-05-20 22:34 730Note: This is an extension of ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 463Given a 2D binary matrix fill ... -
Leetcode - Scramble String
2015-05-17 14:22 542Given a string s1, we may repre ... -
Leetcode - Regular Expression Matching
2015-05-16 16:31 386Implement regular expression ma ... -
Leetcode - Distinct Subsequences
2015-05-01 16:56 463Given a string S and a string T ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-04-23 09:59 0public class Solution ... -
Leetcode - Best Time to Buy and Sell Stock III
2015-04-23 09:04 445Say you have an array for whi ... -
Leetcode - Dungeon Game
2015-04-21 09:50 414The demons had captured the pr ...
相关推荐
leetcode题目:Best Time to Buy and Sell Stock II
leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53....
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
股票买卖最佳时机leetcode GitFitCode 配对编码挑战! 买卖股票的最佳时机 让我们弄清楚什么时候买一些股票! 这不应该在现实生活中使用。 现在不管你认为你的算法有多好:)。 我确实鼓励您选择一只您感兴趣的股票,...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode leetcode The optimum C++ solutions for the leetcode 这是我自己写的leetcode的题解,目前已经完成了70%左右,后续部分会很快更新 这里放上来的代码都能保证是最优解(复杂度最优) 当然有些题目因为测试...
leetcode 答案解析 golang解答
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
股票买卖最佳时机leetcode 该存储库包含买卖股票的最佳时间的所有变体。 所有这些练习题都可以在 leetcode 上找到。
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
股票买卖最佳时机leetcode 买卖股票的最佳时机 Java 程序选择在给定的股票价格数组中买卖股票的最佳时间。
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-tag-Tree
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...